Solve the diophantine equation $(n+1)^{2}X+n^2Y=1$ where $n\in\mathbb{N}$.

Question

I having difficulty applying Euclid's algorithm to find a particular solution.

Answer 1

Either $n=2k$ or $n+1=2k$ for some integer $k$.

In the first case, Euclid's algorithm gives:$$\begin{array}{c|c} (2k+1)^2&4k^2\\4k+1&-k\\1 \end{array}$$

Working backwards: \begin{eqnarray*}1&=&(4k+1) +4(-k)\\ &=& (4k+1)+4(4k^2-k(4k+1)\\ &=& (1-4k)(4k+1)+4(4k^2)\\&=& (1-4k)((2k+1)^2-(4k^2))+4(4k^2)\\&=& (1-4k)(2k+1)^2 +(3+4k)(4k^2)\\&=&(1-4k)(n+1)^2+(3+4k)n^2 \end{eqnarray*}

Thus $X=1-2n, Y=3+2n$.

The second case follows exactly the same method, though it is not necessary to repeat it, as substituting the above values for $X,Y$ we find the equation holds for all $n$.

In both cases $n^2, (n+1)^2$ are coprime, so lcm$(n^2, (n+1)^2)=n^2(n+1)^2$. Thus the solutions $$X=1-2n+tn^2,\qquad Y=3+2n-t(n+1)^2,\qquad t\in \mathbb{Z},$$ cover all cases.