2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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}\ \ $ $\endgroup$ – Bill Dubuque Mar 16 at 16:19
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.