Solving nonlinear Diophantine equations with Euclid's Lemma

Question

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.

Answer 1

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$.

Answer 2

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}$.

Answer 3

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).