Does this modular congruence have a solution?

Question

Prove that every number in $\mathbb{Z}$ is a solution to the congruence $$x^7 − 2x \equiv x \ \ (\operatorname{mod} 42)$$

As far as I can see, this congruence does not have any solutions (for example if we take $x=3$, the output is incorrect), but the book says I need to prove otherwise. Am I missing something here?

The claim to be proved is indeed false; it is even easier to see that for $x=1$ it fails. — Servaes, Jun 25 '18 at 15:49
the statement is not true. e.g $1^7 - 2(1) - 1 = -2$ is not divisible by $42$ — Jack, Jun 25 '18 at 15:49
In the future, please use mathjax to format your questions. It seems daunting at first, but you’ll pick it up quickly :) — Crosby, Jun 25 '18 at 16:18
The correct congruence is $x^7 \equiv x \pmod{42}$. So $x^7 - 2x \equiv x \pmod{42} \iff x \equiv 0 \pmod{21}$. — Daniel Fischer, Jun 25 '18 at 17:37
@DanielFischer can you explain how you came to to 0 and 21? For science reasons :) Thanks to everyone else for the feedback! Appreciate it — Courtney Mill, Jun 26 '18 at 13:42
Using $x^7 \equiv x \pmod{42}$ we get $x^7 - 2x \equiv x - 2x \equiv -x \pmod{42}$. And hence $$x^7 - 2x \equiv x \pmod{42} \iff -x \equiv x \pmod{42} \iff 2x \equiv 0 \pmod{42},.$$ Now, $42 \mid 2x \iff 21 \mid x$. — Daniel Fischer, Jun 26 '18 at 13:46

Robert Z · Answer 1 · 2018-06-26T14:32:13.403

Yes, the given congruence has solutions, and you are right, $x=3$ is not one of them.

In order to find them, since $42=2\cdot 3\cdot 7$, it follows that the congruence is equivalent to the system $$\begin{cases} x^7 − 3x \equiv 0 &\pmod{2}\\ x^7 − 3x \equiv 0 &\pmod{3}\\ x^7 − 3x \equiv 0 &\pmod{7} \end{cases} \Leftrightarrow \begin{cases} x-x \equiv 0 &\pmod{2}\\ x -0\equiv 0 &\pmod{3}\\ x-3x \equiv 0 &\pmod{7} \end{cases}$$ because, by the Fermat's little theorem, $x^p\equiv x \pmod{p}$ for any prime $p$. Can you take it from here?

Does this modular congruence have a solution?

1 Answers1