Here are all the questions :
1) Solve the linear diophantine $2093x – 4019y = 1$
Done, soutions are couples $(361+4019k,188+2093k)$, $k$ random integer.
2) Consider the congruence
$$(F) : x^{251} \equiv -464 \pmod{4019}$$
2-a) Justify that $4019$ is prime. (done)
2-b) Prove that if $x$ is a solution of $(F)$ then $x^{4018} \equiv 1 \pmod{4019}$ (Done)
2-c) Prove that
$$ (464)^{16} \equiv 2093 \pmod{ 4019} $$
Not Done
2-d) Deduce that
$$x^2 \equiv 361 \pmod{ 4019}$$
Done (assuming (2-c))
2-e) Prove that
$$ x \equiv 19 \pmod{4019} \implies x \text{ is a solution of } (F) $$
Not done
2-f) What are all solutions of the congruence $(F)$ ?
Not done (How to disqualify the case $x \equiv -19 \pmod{4019} $ ? )
Thanks for any ideas, hints.
Best Answer
The idea is: $\,\color{#c00}{251\cdot 16\,\equiv\, -2}\pmod{\!4018}\,$ so we have modulo the prime $4019\!:$
$\ \ \left[ x^{\large \color{#c00}{251}}\equiv -464 \right]^{\color{#c00}{\large 16}}\!\Rightarrow\, x^{\color{#c00}{\large -2}}\equiv 2093$ $\iff x^{\large 2}\equiv \dfrac{1}{2093}\equiv 361\equiv 19^{\large 2}\iff x\equiv \pm19$
Both $\pm 19$ aren't roots, else $\, -464 \equiv (-19)^{251}\equiv - 19^{251}\equiv 464\,$ so $\,2(464)\equiv 0\,\Rightarrow\, 464\equiv 0,\,$ contradiction (or $ $ use the uniqueness of $k$'th roots when $k$ is coprime to $\phi,\,$ which further shows$\, x\equiv (-464)^{\large \color{#0a0}{2001}}\,$ by $\bmod 4018\!:\ \dfrac{0}{4018}\overset{\large\frown}\equiv\dfrac{1^{\phantom{|^|}}}{\color{#c00}{251}}\overset{\large\frown}\equiv\color{#c00}{\dfrac{-16}2} \overset{\large\frown}\equiv\dfrac{\color{#0a0}{2001}}1\, $ by here, which reveals the Euclidean genesis of the idea).