First you need to make sure that newton's momentum isn't conserved here so you test this in a case of two balls travelling towards eachother. What you will notice is that momentum is conserved in coordinate system $xy$ and is not conserved in coordinate system $x'y'$.
Here is how you prove that momentum is conserved in $xy$ ($p_1$ is momentum before collision and $p_2$ is momentum after collision):
$$
\scriptsize
\begin{split}
p_1 &= \left[m_A v_{A1x} + m_{B} v_{B1x}\, \bigl| \, 0\right] = \left[m v- m v\, \bigl| \, 0\right] = m\left[v-v \, \bigl| \, 0 \right]=m\left[0 \, \bigl| \, 0 \right] \\
p_2 &= \left[m_A v_{A2y} + m_{B} v_{B2y} \, \bigl| \, 0 \right] = \left[m v - mv \, \bigl| \, 0 \right] = m\left[v-v \, \bigl| \, 0 \right]=m\left[0 \, \bigl| \, 0 \right] \\
\\p_1 &= p_2
\end{split}
$$
I used quotes like $[~~|~~]$ just to sepparate $x$ and $y$ components of momentum like this $p_1=[p_{1x}|p_{1y}]$.
Now you proove that momentum in coordinate system $x'y'$ isn't conserved. Here you must pay a great deal on coordinate system travelling from left to right at all times - even after the collision (see the picture). This means that after collision both balls will allso have $x'$ components. Here is the proof of inequality:
Before collision:
$$
\scriptsize
\begin{split}
p_1' &= \left[ m_A v_{A1x}' + m_B v_{B1x}'\, \biggl| \, 0 \right] = \left[ m_A 0 + m_B \left( \frac{v_{B1x} - u}{1-v_{B1x}\frac{u}{c^2}} \right)\, \biggl| \, 0 \right]= m \left[\left( \frac{-v - v}{1+ v \frac{v}{c^2}} \right) \, \biggl| \, 0 \right] =~~~\\
&= m\left[ - 2v \left( \frac{1}{1+ \frac{v^2}{c^2}}\right) \, \biggl| \, 0 \right]
\end{split}
$$
After collision:
$$
\scriptsize
\begin{split}
p_2' &= \left[-2mv \, \biggl| \,m_A v_{A2y}' + m_B v_{B2y}'\right]=\\
&=\left[ -2mv \, \biggl| \, m_A \left( \frac{v_{A2y}}{\gamma \left(1 - v_{A2x} \frac{u}{c^2}\right)} \right) + m_B \left( \frac{v_{B2y}}{\gamma \left(1 - v_{B2x} \frac{u}{c^2}\right)} \right) \right]=\\
&= \left[ -2mv \, \biggl| \, m \left( \frac{v}{\gamma \left(1 - 0 \frac{v}{c^2}\right)} \right) - m \left( \frac{v}{\gamma \left(1 - 0 \frac{v}{c^2}\right)} \right)\right]= m\left[ -2v \, \biggl| \, \left( \frac{v}{\gamma} \right) - \left( \frac{v}{\gamma} \right)\right]=\\
&= m \left[ -2v \, \biggl| \, 0 \right]
\end{split}
$$
You will notice that equations differ for a factor of $1/(1+ v^2/c^2)$ and it means that classical momentum is not appropriate for relativity as it isnt conserved in all coordinate systems.
Now you write down an inequality just found out, do some algebra and you predict that you can change sign $\neq$ with $=$ if you multiply both sides of inequality equation by some function... i used notation $\gamma(v)$.
$$
\scriptsize
\begin{split}
m\left[ -2v \left( \frac{1}{1+\frac{v^2}{c^2}} \right) \, \biggl| \, 0 \right] &\neq m \left[-2v \, \biggl| \, 0 \right]\\
-2 mv \left( \frac{1}{1+\frac{v^2}{c^2}} \right) &\neq -2 mv\\
\frac{-2 mv}{1+\frac{v^2}{c^2}} &\neq -2 mv\\
\gamma(v) \, \frac{-2 mv}{1+\frac{v^2}{c^2}} &= -2 mv \, \gamma(v)\\
\end{split}
$$
We found out that the function $\gamma(v)$ is actually like this (i don't know exactly how scientists calculated it or derived it, but they found it):
$$
\scriptsize
\gamma(v) = \frac{1}{\sqrt{1-\frac{v^2}{c^2}}}
$$
CAUTION: $v$ is not a relative speed of coordinate systems mooving relative to eachother (which i denote usualy by $u$) but it is a full speed of an object in some coordinate system.
Now you only need a proof to proove that this function is the one. And here is the finale. Because in $\gamma(v)$ there is a full speed you first calculate full speed $v$ for an object before and after collision in coordinate system $x'y'$ and then use those to proove that if you multiply inequality equation above with $\gamma(v)$ you get equality. I choose only one object (that is ball with mass $m_A$) and check its momentum before and after the collision:
Full speed of $m_A$ in $x'y'$ before collision:
$$
\scriptsize
v = -2v \left( \frac{1}{1+\frac{v^2}{c^2}} \right)= \frac{-2v}{1+\frac{v^2}{c^2}}\\
$$
Full speed of $m_A$ in $x'y'$ after collision:
$$
\scriptsize
\begin{split}
v&=\sqrt{(-v)^2 + \left(\frac{v}{\gamma}\right)^2}=v \sqrt{1+ \frac{1}{\gamma^2}} =\\
&= v \sqrt{ 1 + \left(1 - \frac{u^2}{c^2}\right)} = v \sqrt{2 - \frac{v^2}{c^2}}
\end{split}
$$
And the proof that momentum of ball with mass $m_A$ is conserved now:
$$
\begin{split}
\gamma \! \left(\frac{-2v}{1+\frac{v^2}{c^2}}\right) \, \frac{-2mv}{1 + \frac{v^2}{c^2}} &= -2mv \, \gamma \! \left(v \sqrt{2-\frac{v^2}{c^2}}\right)\\
\frac{1}{\sqrt{1- \frac{\left\{-2v/\left(1+v^2\!/\!c^2\right)\right\}^2}{c^2}}} \, \frac{-2mv}{1 + \frac{v^2}{c^2}} &= -2mv \, \frac{1}{\sqrt{1-\frac{\left\{v\sqrt{2-v^2\!/\!c^2}\right\}^2}{c^2}}}\\
\frac{1}{\sqrt{1- \frac{\left\{-2v/\left(1+v^2\!/\!c^2\right)\right\}^2}{c^2}}} \, \frac{1}{1 + \frac{v^2}{c^2}} &= \frac{1}{\sqrt{1-\frac{\left\{v\sqrt{2-v^2\!/\!c^2}\right\}^2}{c^2}}}\\
\frac{1}{1- \frac{\left\{-2v/\left(1+v^2\!/\!c^2\right)\right\}^2}{c^2}} \, \frac{1}{\left(1 + \frac{v^2}{c^2}\right)^2} &= \frac{1}{1-\frac{\left\{v\sqrt{2-v^2\!/\!c^2}\right\}^2}{c^2}}\\
\frac{1}{1- \frac{4v^2}{c^2 \left(1+v^2\!/\!c^2\right)^2}} \, \frac{1}{\left(1 + \frac{v^2}{c^2}\right)^2} &= \frac{1}{1-\frac{v^2\left(2-v^2\!/\!c^2\right)}{c^2}}\\
\frac{1}{\frac{c^2 \left(1+v^2\!/\!c^2\right)^2-4v^2}{c^2 \left(1+v^2\!/\!c^2\right)^2}} \, \frac{1}{\left(1 + \frac{v^2}{c^2}\right)^2} &= \dots\\
\frac{{\bigl(1+\frac{v^2}{c^2}\bigl)}^2}{\frac{c^2 \left(1+v^2\!/\!c^2\right)^2-4v^2}{c^2}} \, \frac{1}{\left(1 + \frac{v^2}{c^2}\right)^2} &= \dots\\
\frac{1}{\frac{c^2 \left(1+v^2\!/\!c^2\right)^2-4v^2}{c^2}} &= \dots\\
\frac{1}{\frac{c^2 \left(1+2v^2\!/\!c^2+v^4\!/\!c^4\right)-4v^2}{c^2}} &= \dots\\
\frac{1}{\frac{c^2+2v^2+v^4\!/\!c^2-4v^2}{c^2}} &= \dots\\
\frac{1}{\frac{c^2-2v^2+v^4\!/\!c^2}{c^2}} &= \dots\\
\frac{1}{\frac{c^2}{c^2} - 2\frac{v^2}{c^2} + \frac{v^4}{c^4}} &= \dots\\
\frac{1}{1 - \frac{v^2}{c^2} \left( 2 - \frac{v^2}{c^2} \right)} &= \dots\\
\frac{1}{1 - \frac{v^2 \left( 2 - v^2\!/\!c^2 \right)}{c^2}} &= \frac{1}{1-\frac{v^2\left(2-v^2\!/\!c^2\right)}{c^2}}\\
\end{split}
$$
Wohoho now we have equality all of a sudden. Well thats what we wanted right? This is the proof that equation $p=\gamma(v)mv$ is the one to replace $p=mv$.
This is really step by step using easy algebra. I used ˝$\dots$˝ where i didn't change anything compared to a line above.