Return to Answer

This answer (which I made Community Wiki) attempts an explicit summary of how to ``list" explicitly the solutions of the given equation, given the answer of Robert Israel and the comment of David Speyer which followed it.

It's convenient to deal with the prime $2$ first, but this is easy, because the only condition imposed on $z$ to get the right power of $2$ dividing $z^{2}+1$ is that if $x$ is odd, we need $z$ odd.

If $p$ is an odd prime such that $p^{n}$ is the exact power of $p$ dividing $x^{2}+1$, then we just require that $p^{n}$ divides $z^{2} -x^{2}$, so we need $ z \equiv \pm x$ (mod $p^{n}$) since $p$ is odd.

Notice then that, in all cases, there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct odd primes dividing $x^{2}+1$.

To be more explicit, if $x$ is even, let the prime factorization of $x^{2}+1$ be $x^{2}+1 = \prod_{i=1}^{k}p_{i}^{n_{i}}$, where the $p_{i}$ are distinct primes, and if $x$ is odd, let the prime factorization of $\frac{x^{2}+1}{2}$ be $\frac{x^{2}+1}{2} = \prod_{i=1}^{k}p_{i}^{n_{i}}$.

For any ordered $k$-tuple of signs $(\epsilon_{1}, \ldots, \epsilon_{k})$, solve (simultaneously) $z \equiv \epsilon_{i} x$ (mod $p_{i}^{n_{i}}$) for each $i$. If $x$ is odd, also impose the condition that $z$ is odd.

In either case, this gives $2^{k}$ distinct possibilities for the congruence of $z$ (mod $x^{2}+1$) which yield $x^{2} + 1 | z^{2}+1$, and there are no other valid congruences (where, as noted earlier, $k$ is the number of distinct odd prime divisors of $x^{2}+1$).

This answer (which I made Community Wiki) attempts an explicit summary of how to ``list" explicitly the solutions of the given equation, given the answer of Robert Israel and the comment of David Speyer which followed it.

It's convenient to deal with the prime $2$ first, but this is easy, because the only condition imposed on $z$ to get the right power of $2$ dividing $z^{2}+1$ is that if $x$ is odd, we need $z$ odd.

If $p$ is an odd prime such that $p^{n}$ is the exact power of $p$ dividing $x^{2}+1$, then we just require that $p^{n}$ divides $z^{2} -x^{2}$, so we need $ z \equiv \pm x$ (mod $p^{n}$) since $p$ is odd.

Notice then that, in all cases, there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct odd primes dividing $x^{2}+1$.

To be more explicit, if $x$ is even, let the prime factorization of $x^{2}+1$ be $x^{2}+1 = \prod_{i=1}^{k}p_{i}^{n_{i}}$, where the $p_{i}$ are distinct primes, and if $x$ is odd, let the prime factorization of $\frac{x^{2}+1}{2}$ be $\frac{x^{2}+1}{2} = \prod_{i=1}^{k}p_{i}^{n_{i}}$.

For any ordered $k$-tuple of signs $(\epsilon_{1}, \ldots, \epsilon_{k})$, solve (simultaneously) $z \equiv \epsilon_{i} x$ (mod $p_{i}^{n_{i}}$) for each $i$. If $x$ is odd, also impose the condition that $z$ is odd.

In either case, this gives $2^{k}$ distinct possibilities for the congruence of $z$ (mod $x^{2}+1$) which yield $x^{2} + 1 | z^{2}+1$, and there are no other valid congruences (where, as noted earlier, $k$ is the number of distinct odd prime divisors of $x^{2}+1$).

For each integer $r$ and each integer $m \neq 0$ let $S(m,r)$ be the set of integers $0\leq w<|m|$ such that $w^2 \equiv r \,(\text{mod } m)$. We have just explicitly described the set $S(x^2+1,-1)$ for any integer $x$. Using it, the complete solution set to our equation is given by $x=u$, $z=(u^2+1)v + r$ and $y=(u^2+1)v^2 + 2vr + \frac{r^2+1}{u^2+1}$ for $u,v \in {\mathbb Z}$ and $r \in S(u^2+1,-1)$.

As noted by David Speyer following Robert Israel's answer, given the factorization of $x^{2}+1$, then it is not necessary to find square roots of $-1$ mod prime powers.

It's convenient to deal with the prime $2$ first, but this is easy, because the only condition imposed on $z$ to get the right power of $2$ dividing $z^{2}+1$ is that if $x$ is odd, we need $z$ odd.

If $p$ is an odd prime such that $p^{n}$ is the exact power of $p$ dividing $x^{2}+1$, then we just require that $p^{n}$ divides $z^{2} -x^{2}$, so we need $ z \equiv \pm x$ (mod $p^{n}$) since $p$ is odd.

Notice then that, in all cases, there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct odd primes dividing $x^{2}+1$.

To be more explicit, if $x$ is even, let the prime factorization of $x^{2}+1$ be $x^{2}+1 = \prod_{i=1}^{k}p_{i}^{n_{i}}$, where the $p_{i}$ are distinct primes, and if $x$ is odd, let the prime factorization of $\frac{x^{2}+1}{2}$ be $\frac{x^{2}+1}{2} = \prod_{i=1}^{k}p_{i}^{n_{i}}$.

For any ordered $k$-tuple of signs $(\epsilon_{1}, \ldots, \epsilon_{k})$, solve (simultaneously) $z \equiv \epsilon_{i} x$ (mod $p_{i}^{n_{i}}$) for each $i$. If $x$ is odd, also impose the condition that $z$ is odd.

In either case, this gives $2^{k}$ distinct possibilities for the congruence of $z$ (mod $x^{2}+1$) which yield $x^{2} + 1 | z^{2}+1$, and there are no other valid congruences (where, as noted earlier, $k$ is the number of distinct odd prime divisors of $x^{2}+1$).

This answer (which I made Community Wiki) attempts an explicit summary of how to ``list" explicitly the solutions of the given equation, given the answer of Robert Israel and the comment of David Speyer which followed it.

It's convenient to deal with the prime $2$ first, but this is easy, because the only condition imposed on $z$ to get the right power of $2$ dividing $z^{2}+1$ is that if $x$ is odd, we need $z$ odd.

If $p$ is an odd prime such that $p^{n}$ is the exact power of $p$ dividing $x^{2}+1$, then we just require that $p^{n}$ divides $z^{2} -x^{2}$, so we need $ z \equiv \pm x$ (mod $p^{n}$) since $p$ is odd.

Notice then that, in all cases, there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct odd primes dividing $x^{2}+1$.

To be more explicit, if $x$ is even, let the prime factorization of $x^{2}+1$ be $x^{2}+1 = \prod_{i=1}^{k}p_{i}^{n_{i}}$, where the $p_{i}$ are distinct primes, and if $x$ is odd, let the prime factorization of $\frac{x^{2}+1}{2}$ be $\frac{x^{2}+1}{2} = \prod_{i=1}^{k}p_{i}^{n_{i}}$.

For any ordered $k$-tuple of signs $(\epsilon_{1}, \ldots, \epsilon_{k})$, solve (simultaneously) $z \equiv \epsilon_{i} x$ (mod $p_{i}^{n_{i}}$) for each $i$. If $x$ is odd, also impose the condition that $z$ is odd.

In either case, this gives $2^{k}$ distinct possibilities for the congruence of $z$ (mod $x^{2}+1$) which yield $x^{2} + 1 | z^{2}+1$, and there are no other valid congruences (where, as noted earlier, $k$ is the number of distinct odd prime divisors of $x^{2}+1$).

If you allow the factorization of $x^{2}+1$, then I don't think it is even necessary to find square roots of $-1$ mod prime powers.

It's convenient to deal with the prime $2$ first, but this is easy, because the only condition imposed on $z$ to get the right power of $2$ dividing $z^{2}+1$ is that if $x$ is odd, we need $z$ odd.

If $p$ is an odd prime such that $p^{n}$ is the exact power of $p$ dividing $x^{2}+1$, then we just require that $p^{n}$ divides $z^{2} -x^{2}$, so we need $ z \equiv \pm x$ (mod $p^{n}$) since $p$ is odd.

Notice then that, in all cases, there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct odd primes dividing $x^{2}+1$.

As noted by David Speyer following Robert Israel's answer, given the factorization of $x^{2}+1$, then it is not necessary to find square roots of $-1$ mod prime powers.

It's convenient to deal with the prime $2$ first, but this is easy, because the only condition imposed on $z$ to get the right power of $2$ dividing $z^{2}+1$ is that if $x$ is odd, we need $z$ odd.

If $p$ is an odd prime such that $p^{n}$ is the exact power of $p$ dividing $x^{2}+1$, then we just require that $p^{n}$ divides $z^{2} -x^{2}$, so we need $ z \equiv \pm x$ (mod $p^{n}$) since $p$ is odd.

Notice then that, in all cases, there are $2^{k}$ possible congruences for $z$ (mod $x^{2}+1$), where $k$ is the number of distinct odd primes dividing $x^{2}+1$.

To be more explicit, if $x$ is even, let the prime factorization of $x^{2}+1$ be $x^{2}+1 = \prod_{i=1}^{k}p_{i}^{n_{i}}$, where the $p_{i}$ are distinct primes, and if $x$ is odd, let the prime factorization of $\frac{x^{2}+1}{2}$ be $\frac{x^{2}+1}{2} = \prod_{i=1}^{k}p_{i}^{n_{i}}$.

For any ordered $k$-tuple of signs $(\epsilon_{1}, \ldots, \epsilon_{k})$, solve (simultaneously) $z \equiv \epsilon_{i} x$ (mod $p_{i}^{n_{i}}$) for each $i$. If $x$ is odd, also impose the condition that $z$ is odd.

In either case, this gives $2^{k}$ distinct possibilities for the congruence of $z$ (mod $x^{2}+1$) which yield $x^{2} + 1 | z^{2}+1$, and there are no other valid congruences (where, as noted earlier, $k$ is the number of distinct odd prime divisors of $x^{2}+1$).