# Solving nonlinear Diophantine equations with Euclid's Lemma

How do I use Euclid's Lemma to solve the Diophantine equation $$x^2 \equiv 13$$ mod $$17$$? From there, how do I solve the Diophantine equation $$s^2 \equiv 13$$ mod $$289$$?

Thanks in advance for any help.

How do I use Euclid's Lemma to solve the Diophantine equation $$x^2\equiv 13 \pmod{17}$$?

This is not a Diophantine equation, but a congruence. Since $$13\equiv 30\equiv 47\equiv 64\pmod{17}$$, the congruence is equivalent to $$x^2\equiv 64\pmod{17}$$; that is, to $$(x-8)(x+8)\equiv 0\pmod{17}$$; in other words, to $$17\mid (x-8)(x+8)$$ (where $$x$$ denotes an integer solution of the congruence). By Euclid's lemma, this is equivalent to $$17\mid x-8$$ or $$17\mid x+8$$; equivalently, to $$x\equiv\pm8\pmod{17}$$.

• $13 \equiv \color{#c00}{-1}\cdot 2^{\large 2}\,$ and $\,\color{#c00}{-1\equiv 4^{\large 2}}\,\Rightarrow\, 13\equiv \color{#c00}{4^{\large 2}} 2^{\large 2}\equiv 8^{\large 2}\ \$ – Bill Dubuque Mar 16 at 16:19

I don't see how to use Euclid's lemma to find a square root of $$13\bmod 17$$. However , writing the squares of $$\pm2,\dots,\pm 8\bmod 17$$, it's not very long to check that $$13 \;(\equiv -4)$$ has for square roots $$\pm8\bmod 17$$.

For the second question, as $$289=17^2$$, you can use Hensel's lifting:

Let $$p$$ be a prime. If $$r$$ is a root modulo $$p^n$$ of the polynomial $$f(X)\in\mathbf Z[X]$$, such that $$f'(r)\not\equiv 0\mod p$$, then $$r$$ can be lifted to a root $$r_1$$ of $$f(X) \bmod p^{2n}$$. Moreover this root is unique $$\bmod p^{2n}$$, and it is given by $$r_1=r-f(r)s\mod p^{2n},$$ where $$s$$ is the inverse of $$f'(r)\bmod p^n$$.

You are trying to solve congruences, not diophantine equations. Since you are a new contributor, I detail all the arguments.

1) Your first congruence $$x^2 \equiv 13\equiv -4$$ mod $$17$$ can be viewed as an equation $$[x]^2+[4]=[0]$$ in the finite field $$\mathbf F =\mathbf Z/17\mathbf Z$$. Since the multiplicative group of a finite field is cyclic, $$\mathbf F^*$$ admits a unique subgroup of order $$4$$, generated by $$[4]$$ (check that $$4^2\equiv -1$$, so we may think of $$[4]$$ as an analog of $$\sqrt {-1}$$ in $$\mathbf C$$), and our equation in classes becomes $$[x]^2-4[4]^2=([x]+2[4])([x]-2[4])=[0]$$, which is equivalent to $$[x]=\pm [8]$$ because we work inside a field (this amounts here to what you call Euclid's lemma).

2) We can try to apply the same tactics to your second congruence $$x^2 \equiv 13$$ mod $$289$$, but this time it fails because $$289={17}^2$$ and the ring $$R=\mathbf Z/{17}^2\mathbf Z$$ is no longer a field, not even a domain. The way out is to work inside the multiplicative group $$R^*$$ of invertible elements of $$R$$, noting that the class $$[13]$$ mod $${17}^2$$ is invertible because $$17$$ does not divide $$13$$. The structure of $$R^*$$ is known. Quite generally, for an odd prime $$p$$ and an integer $$n\ge 1$$, it is known that $$(\mathbf Z/p^n\mathbf Z)^*$$ is the direct product of the cyclic subgroup of order $$p^{n-1}$$generated by the class of $$1+p$$ and a cyclic group of order $$p-1$$ (this is more precise than the Euler totient function; see e.g. Lang's "Algebra", chap. II, ex. 7). In your case here, $$R^*\cong C_{17}\times C_{16}$$ and, to solve $$[x]_{289}=({[13]_{289}})^2$$, we just have to project onto the the direct components and solve an equation of the form $$a=b^2$$ in $$C_{17}$$, as well as $$[x]_{17}=({[13]_{17}})^2$$ in $$C_{16}$$. Because $$17$$ is odd, the first equation admits only the solution $$1=1$$; as for the second equation, it has already been solved in 1).