# Solving Pell's equation(or any other diophantine equation) through modular arithmetic.

Let us take a solution of Pell's equation ($x^2 - my^2 = 1$) and take any prime $p$. Then we have found a solution of the Pell's equation mod $p$.

Now, conversely, for any prime $p$, we can find a solution of Pell's equation. My question is whether we can use these solutions mod $p$ to build a solution in the integers.

About the general matter of deriving the existence of solutions over $\Bbb Q$ from solutions modulo every prime it is worth recalling the classical theorem in Number Theory that goes under the name of Hasse's Principle that a quadratic form $$F(X_1,..X_n)=\sum_{1\geq i\geq j\geq n}a_{ij}X_iX_j\in\Bbb Q[X_1,...,X_n]$$ represents $0$ (i.e. admits a non-trivial solution of $F(X_1,..X_n)=0$ in $\Bbb Q^n$) if and only if it represents $0$ over $\Bbb R$ and all the $p$-adic fields $\Bbb Q_p$.

In turn, to go from a solution mod $p$ to a solution in $\Bbb Q_p$ one has to apply Hensel's Lemma.

Mind, though, that the proofs are not constructive. E.g., see Serre's book A Course in Arithmetic, Springer GTM 7.

These general results do apply to Pell's equation, because one can homogenize it, i.e. solving $X^2-mY^2=1$ is equivalent to find a representation of $0$ of $$X^2-mY^2-Z^2.$$ Nonetheless, they are not too conclusive, in the sense that they do not allow to say that there exist solutions of Pell's equation different from the trivial ones, namely $X=\pm1$, $Y=0$.

• Yes, this proves existence of a solution to Pell's equation... but not promising a "non-trivial" one, because $X=1$, $Y=0$, $Z=1$ would already fulfill the Hasse-principle criteria. – paul garrett Jun 17 '13 at 12:31
• @paulgarrett : That is actually true. I was more intent in addressing the "local-to-global" question. I guess I'll have to edit the last part of my answer. – Andrea Mori Jun 17 '13 at 14:29
• It would be interesting if somehow the existential part could be made to avoid the trivial solution in this example... – paul garrett Jun 17 '13 at 15:34

For each $p$, Pell's equation will have many solutions modulo $p$. There wil be no way to tell which solution mod one prime matches up with which solution modulo another, so you won't be able to use the Chinese Remainder Theorem to glue the solutions together.

Not only can you not build a solution-- a solution mod p need not correspond to a solution in $\mathbb{Z}$. For example, let $p=19, m=3$. Then $0^2-3(5^2) \equiv -75 \equiv 1 \pmod{p}$, so $(0,5)$ is a solution mod 19. However, in the integers, all solutions to $x^2 -3 y^2=1$ are generated by the solution $(2,1)$, up to sign. But the powers of $(2,1)$, mod 19, are: $(2,1), (7,4), (7,15), (2,18), \textrm{ and } (1,0)$. (These are really the powers of $2+\sqrt{3}$.) In particular, the first component is never $0$, so no matter how we change signs, we can never get the solution $(0,5)$ from a solution to $x^2-3y^2$ over $\mathbb{Z}$.