# Find the positive integral solution of indefinite equation

Equation: $X^2+Y^2=Z^2+1$
How to find all positive integer solutions to this equation.

Can you find $n\in \mathbb{N}$ such that $X^2+Y^2=Z^2+n$ has no positive integers as solutions ?

-
Please be polite and do not post in the imperative. What have you tried? –  user38268 Aug 25 '11 at 6:37

There is no such $n$. Rewrite as $y^2-n=z^2-x^2$. Choose $y$ so left side is positive and not twice an odd number (always possible: just take $y$ of parity opposite to $n$), every such number can be written as a difference of 2 squares. Even easier: let $x=(n^2+n)/2$, $y=n+1$, $z=(n^2+n+2)/2$.

EDIT: Concerning the first question, some of the discussion at this MathOverflow question might be of interest.

-

Gerry Myerson has dealt with the second question. I will say a few words about the first. The ring of Gaussian Integers, that is $\mathbb{Z}[i],$ is the natural place to address this question. Many algebra texts use this ring to prove that a prime $p \equiv 1$ (mod 4) is a sum of two (rational integer) squares. The ring of Gaussian integers, is a Euclidean domain, hence a unique factorization domain. Its arithmetic is complicated somewhat by the existence of the four units $\{1,-1,i,-i\},$ and uniqueness of prime factorizations is only up to reordering of terms and multiplication of terms by a unit. It has three kinds of prime: rational primes $p \equiv 3$ (mod 4) remain prime in $\mathbb{Z}[i],$ primes $p \equiv 1$ (mod 4) are expressible as a product of two different primes in $\mathbb{Z}[i],$ so when $p \equiv 1$ (mod 4), we can always write $p = (a+bi)(a-bi)$ for coprime (rational) integers $a$ and $b$ (note that also $p = (b+ai)(b-ai)$). In this case, we have ${\rm gcd}(a+bi,a-bi) = 1$ in $\mathbb{Z}[i].$ The prime $2$ is very special in $\mathbb{Z}[i].$ We have $2 = (1+i)(1-i) = -i(1+i)^2,$ so $2$ is a unit times the square of a prime element of $\mathbb{Z}[i].$

To solve $X^2 + Y^2 = Z^2 + 1$ in rational integers, we note the following: (*) For any even integer $Z$, the integer $Z^2 + 1$ is a product of primes which are each congruent to $1$ (mod $4$). For note that $Z^2 + 1$ is odd, so that neither $Z+i$ nor $Z -i$ can have a factor $1+i$ in $\mathbb{Z}[i]$ (if one did, taking complex conjugates shows that the other one does, since $1+i$ divides $1-i$). If $p$ were a prime congruent to $3$ (mod 4), which divided $Z^2+1$, then in $\mathbb{Z}[i],$ we have $p$ divides $(Z+i)(Z-i),$ so since $p$ remains prime in the Euclidean domain $\mathbb{Z}[i],$ we have $p$ divides $Z+i$ or $p$ divides $Z-i.$ But, taking complex conjugates, if it divides one, then it divides the other. Then $p$ divides $Z+i -(Z-i),$ so that $p$ divides $2i$, a contradiction (this is one way that $2$ behaves differently).

(**) For any odd integer $Z$, the integer $Z^2+1$ is divisible by $2$, but not $4,$ and its remaining (rational) primes factors are all congruent to $1$ (mod 4). The statement about odd prime factors follows as above, and we note that $Z^2+1$ is congruent to $2$ (mod 4) when $Z$ is odd, so $Z^2+1$ is divisible by $2$, but not by $4,$ in that case.

Returning to the original question, there are two cases to consider: if $Z$ is even, we know we can factorize $Z^2 + 1$ in the form $p_1^{m_1} \ldots p_n^{m_n}$ where the $p_j$ are distinct (rational) primes, each congruent to $1$ (mod 4). For each $j,$ we may write $p_j = \pi_j \overline{\pi_{j}},$ where each $\pi_j = a_j + ib_j$ for rational integer $a_j$ and $b_j$, and each $\pi_j$ is a prime element of $\mathbb{Z}[i].$

If $Z$ is odd, we can factorize $Z^2 + 1$ in the form $2.p_1^{m_1} \ldots p_n^{m_n}$ where the $p_j$ are distinct (rational) primes, each congruent to $1$ (mod 4). For each $j,$ we may write $p_j = \pi_j \overline{\pi_{j}},$ where each $\pi_j = a_j + ib_j$ for rational integer $a_j$ and $b_j$, and each $\pi_j$ is a prime element of $\mathbb{Z}[i].$ We can also write $2 = \pi_0 \overline{\pi}_0,$ where $\pi_0 = (1+i)$.

Hence we have (in $\mathbb{Z}[i]$), a prime factorization of $(Z+i),$ which is as unique as it can be, which , (possibly after switching $\pi_j$ and $\overline{\pi}_j$ and relabelling), has the form $Z+i = \pi_0 ^{\delta} \prod_{j=1}^{n} \pi_{j}^{m_j},$ where $\delta = 0$ if $Z$ is even, and $\delta = 1$ if $Z$ is odd.

Then a way to solve $X^2 + Y^2$ in rational integers is to write $X^2 + Y^2 = (X+iY)(X-iY)$ in $\mathbb{Z}[i].$ If we factorize $X + iY$ as a proudct of primes in $\mathbb{Z}[i],$ we get a prime factorization of $X-iY$ by complex conjugation, and then juxtaposing them gives a prime factorization of $Z^2 + 1,$ so we can exploit the uniqueness.

Up to multiplication by a unit, we must have $X + iY = \pi_{0}^{\delta} \prod_{j = 1}^{n} \pi_{j}^{r_j}\overline{\pi}_{j}^{s_j}$, where for each $j,$ we have $r_j \leq m_j$ and $s_j \leq m_j.$ Taking complex conjugates gives $X-iY$ in a similar form. Now we notice that for each $j$, we must have $r_j + s_j =m_j,$ to get the right prime factorization for $Z+i.$

Then we use $2X = (X+iY) +(X-iY)$ and $2Y= -i(X+iY) +i(X-iY)$ to calculate $X$ and $Y$.

In summary, all solutions can be found as follows: choose any positive integer $Z$, and factorize $Z+i$ in $\mathbb{Z}[i]$. This factorization will (up to multiplication by a unit) have the form $Z+i = \pi_0 \prod_{j=1}^{n} \pi_j ^{m_j}$, where $\pi_0 = i+i$ and $\delta = 0,1$ if $Z$ is even, odd respectively, and where there are $n$ distinct (rational) primes $p_j,$ each congruent to $1$ (mod 4), such that $p_j = |\pi_j|^2$ for each $j,$ each $\pi_j$ being a Gaussian integer. We may then choose $X+iY$ to be any expression of the form $\pi_0^{\delta} \prod_{j=1}^{n} \pi_{j}^{r_j} \overline{\pi_j}^{m_j - r_j}$, where $0 \leq r_j \leq m_j$ for each $j.$ Since you insist that $X$ and $Y$ be positive, it may be necessary to replace $X$ by $-X$, etc.

-
I imagined OP to be asking for parametric formulas giving all solutions, like the formulas $\lbrace x,y\rbrace=\lbrace2kmn,k(m^2-n^2)\rbrace$, $z=k(m^2+n^2)$ for $x^2+y^2=z^2$. I don't know if there are any. –  Gerry Myerson Aug 25 '11 at 12:55
But your link which you edited in to your answer in seems to suggest (strongly) that there is a parametrization. –  Geoff Robinson Aug 26 '11 at 23:47
There is a parametrization, but it's a bit of a cheat, as the parameters are related by $rt+su=2$, and how do you parametrize that? –  Gerry Myerson Aug 27 '11 at 1:15
That parametrization and what I am doing seem closely related, come to think of if. Factoring $z+i$ as $(r+si)(t+ui)$ in $\mathbb{Z}[i]$ amounts to writing $z = rt-us$ where $ru+st = 1.$ –  Geoff Robinson Aug 27 '11 at 13:43
Yes, quite.${}$ –  Gerry Myerson Aug 27 '11 at 22:42