elementary number theory - Solving a congruence, tricky implication

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.