Solve for the unknown

Question

$31x-21^{21} \equiv 21+31^{31} \pmod 5$

The provided answers are: $$ \left\{ 3,8,13,18,... \right. $$

but I don't know how to get there. Can someone walk me through this please?

Answer 1

$$\begin{split} 31x-21^{21} &\equiv 21+31^{31} &\pmod{5} \Longleftrightarrow\\ 31x &\equiv 21+21^{21}+31^{31} &\pmod{5} \Longleftrightarrow\\ x &\equiv21 + 21^{21}+31^{31} &\pmod{5} \end{split}$$ Now you have at least two (and half) ways. You can notice that last digit is $1$, so last digit in any component of the sum will be $1$. I believe that you can finish it.

Second way is Fermat's little theorem (Euler's theorem). ($5$ is prime and $\gcd(21,5)=1 $ and $\gcd(31,5)=1$.)

However, you should receive $x \equiv 1+1+1 \pmod{5}$, so $x=5k+3$.

Answer 2

$31x-21^{21} \equiv 21+31^{31} \pmod 5$

Because:

$31 \equiv 21 \equiv 1 \pmod 5$

it's as simple as:

$x - 1^{21} \equiv 1 + 1^{31} \pmod 5$

$x \equiv 1 + 1 + 1 = 3 \pmod 5$

So the solution is $x \equiv 3 \pmod 5$, which is basically what you have there in the listed solution set (well, just the positive values anyway).

Answer 3

I understand the following is not a rigorous method, but its a start- Intuitively, 21^21 always ends with 1, no matter what. 31^31 ends with 1, no matter what. [31x - 21^21 - (21 +31^31)] mod 5 = 0 , implying the result should be divisible by 5 to satisfy the congruence.

This means that the result should end with a 0 or a 5. The one's place in (-21^21), (-21), (-31^31) brings down the congruence by -3 from the nearest zero, and -8 from the nearest 5. Hence, 31*x should be such that the one's place of 31*x should increase the equation value by 3, or by 8. Naturally, the solution sequence would be x =3, 8, 13, 18, etc- (since 31*3 has one's place =3, 31* 8 has 8, and so on.) Hope this makes sense.