Solving a Complex Diophantine Equation with One Known

Question

I am struggling to find a way to implement Euclid's Algorithm in order to solve this diophantine equation. The $N$ will be known and the set of solutions I wish to find will be a set of decreasing $X$ solutions that satisfy $$x^2 - 4 y^2 = n.$$

When simplifying I have concluded that the solution could be as follows... $$x^2 - 4 y^2 = (x - 2y) (x + 2y)$$ when $n = 12$, $$12 = (x - 2y) (x + 2y)$$ would it be possible to use Euclid's Algorithm to solve for the GCD in decreasing order? The poposed solutions are a set of $n=12$, $x = 4$ and $y = 1$.

Answer 1

The following shows that the Pythagorean Theorem can be used here. $$x^2-4y^2=n\implies n+ 4y^2=x^2\\ \rightarrow\quad A^2+B^2=C^2:A=\sqrt{n}, B=2y, C=x\\ \implies n=A^2\quad y=\frac{B}{2}\quad x=C$$ Beginning with Euclid's formula $ \quad A=m^2-k^2,\quad B=2mk,\quad C=m^2+k^2\quad$ we can find solutions by solving for $k$ and test a defined range of $m$-values to see which ones yield integers. Side-$A$ of a Pythagorean triple can be any odd number greater than one and so any $A=(2j+1)$ will yield a triple. Here is the process demonstrated for $A=15$

\begin{equation} A=m^2-k^2\implies k=\sqrt{m^2-A}\\ \text{for}\qquad \lfloor\sqrt{A+1}\rfloor \le m \le \frac{A+1}{2} \end{equation} The lower limit ensures $k\in\mathbb{N}$ and the upper limit ensures $m> k$. $$A=15\implies \lfloor\sqrt{15+1}\rfloor=4\le m \le \frac{15+1}{2} =8\\\land\quad m\in\{4,8\}\implies k \in\{1,7\} $$ $$F(4,1)=(15,8,17)\qquad \qquad F(8,7)=(15,112,113) $$

Translating, we get $\quad (15,8,17)\rightarrow(17,4,225)\qquad (15,112,113)\rightarrow (113,56,225)\quad$ These can be obtained more directly from $(m,k)$ if we adapt Euclid's formula as follows. $$x=m^2+k^2\qquad y=mk\qquad n=(m^2-k^2)^2$$

Notice that $A=\sqrt{n}\space $ lets us put in any odd number for $A\ge3$ and we get the other terms out automatically in translation or by applying the modified formula. Here are a $33$ [primitive] solutions from the first $25$ $n$-values in ascending order of $n.\quad$ e.g. $5^2-4(2^2)=3^2$

$$(5,2,9)\quad (13,6,25)\quad (25,12,49)\quad (41,20,81)\quad (61,30,121)\\ (85,42,169)\quad (17,4,225)\quad(113,56,225)\quad (145,72,289)\quad (181,90,361)\\ (29,10,441)\quad (265,132,529)\quad (221,110,441)\quad (313,156,625)\quad (45,18,729)\\ (365,182,729)\quad (421,210,841)\quad (481,240,961)\quad (65,28,1089)\quad (545,272,1089)\\ (37,6,1225)\quad (613,306,1225)\quad (685,342,1369)\quad (89,40,1521)\quad (761,380,1521)\\ (841,420,1681)\quad (925,462,1849)\quad (53,14,2025)\quad (1013,506,2025)\quad (1105,552,2209)\\ (1201,600,2401)\quad (149,70,2601)\quad (1301,650,2601)\quad $$

This procedure also works for $n=(4x),x>1$ but the results are not primitive.

Answer 2

Say $12=(x+2y)(x-2y)=ab$, where $x$ and $y$ are positive integers,

with $x+2y=a, $ and $x-2y=b$. Then $a>b$, and $2x=a+b$.

That means $a+b$ must be even, so $a$ and $b$ are both odd or both even.

But $a$ and $b$ cannot be both odd, since $ab=12$ is even.

Therefore, $a$ and $b$ are both multiples of $2$.

Since $12=2\times2\times3=ab$, it follows that $a=2\times3$ and $b=2$,

so $x=(a+b)/2=4$ and $y=1$.

Answer 3

In response to your request for the detailed translated answer, you could would it out with algebra but I have more experience with these equations so it will be easier for me. I never heard of "discord" until you asked if I used it and the answer is "no". WolframAlpha is popular on this forum.

In the other answer we identified the "adjusted" Euclid's formula $$x=m^2+k^2\qquad y=mk\qquad n=(m^2-k^2)^2$$

$$n=(m^2-k^2)^2 \quad\implies\quad k = \sqrt{m^2-\sqrt{n} }\\ \text{for}\quad \big\lceil\sqrt{\sqrt{n} - 1}\space\big\rceil \le m\le \frac{\sqrt{n}+1}{2}$$

The lower limit ensures that $k\in\mathbb{N}$ and the upper limit insures that $k<m$

For $n=225$ we know the solutions are $\quad(17,4,225)\land(113,56,225)$

$$n=225\implies \big\lceil\sqrt{\sqrt{225} - 1}\space\big\rceil =4 \le m \le \frac{\sqrt{225}+1}{2}=8\\ \quad\land\quad m\in\{4,8\}\implies k\in\{1,7\}$$

$$ x=m^2+k^2\qquad y=mk\qquad n=(m^2-k^2)^2\implies$$ $$F(4,1)\rightarrow x=4^2+1^2=17\quad y=4(1)=4\quad n=(4^2-1^2)^2=225\\ F(8,7)\rightarrow x=8^2+7^2=113\quad y=8(7)=56\quad n=(8^2-7^2)^2=225$$