We want to prove that
$$243x \equiv 1 \mod 2018 \implies x^{403} \equiv 3 \mod 2018$$
My try :
Assume that $243x \equiv 1 \mod 2018$
We have $x^{2016} \equiv 1 \mod 2018$ (by Fermat ($1009$ is prime) and oddness of $x$) so $x^{2015} \equiv 243 \mod 2018$
but $403 \times 5 = 2015 $
hence $(x^{403})^5 \equiv 243 \mod 2018$ or equivalently $(x^{403})^5 \equiv 3^5 \mod 2018$. I wonder how to get from this last congruence to the desired $x^{403} \equiv 3 \mod 2018$ ?
Thanks for any suggestions.
Answer
From the last step of your attempt i.e. $(x^{403})^5 \equiv 3^5 \mod 2018$, you can go to the conclusion if you can show that $y^5 \equiv 243 \mod 2018$ has only one solution mod $2018$ (because this would force $x^{403} \equiv 3 \mod 2018$ as they are both solutions).
While that statement is true, its proof is not going to be easy because it boils down to asking why $x^5 \equiv 1 \mod 2018$ has a unique solution, and this is not clear at all.
Therefore, you have not done anything wrong but got yourself in a higher power than required.
However, you did do some groundwork. For example, by noting that $243x \equiv 1 \mod 2018$, so we may raise both sides to the power $403$ :
$$
3^5x \equiv 1 \mod 2018 \implies 3^{2015}x^{403} \equiv 1 \mod 2018
$$
Now, multiply by a further $3$, and eliminate the $3^{2016}$ using an argument made in your attempt.
No comments:
Post a Comment