# Modular arithmetic

• I
rashida564
Summary
Find a ∈ Z such that a^6 ≡ a mod 6
Hi everyone, I can find multiple of number for example 2,3,4 and so on. But is there any reason why those number does work.

Mentor
2021 Award
We have ##6 \,|\,a^6-a=a(a^5-1)=a(a-1)(a^4+a^3+a^2+a+1)##, so the divisors of ##6## must be divisors of the factors on the right. E.g. ##a=3,4## are immediately clear, and ##a=2## is wrong, as ##2^6=64 \equiv 4\not\equiv 2 \operatorname{mod}6\,.##

jedishrfu
rashida564
Is it try and error method?

Gold Member
Another way to look at it is that your congruence is equivalent to the two simultaneous congruences ##a^6\equiv a \mod 2## and ##a^6\equiv a\mod 3##. The first congruence is always true, and the second is true when ##a\equiv 0,1\mod 3##, but fails when ##a\equiv 2\mod 3##.

jedishrfu and mfb
Mentor
2021 Award
Is it try and error method?
Where did you see try and error? Factorization to investigate factors is a quite natural thing.

##a^6\equiv a \operatorname{mod} 6 ## is defined as ##6\,|\,a^6-a##, so factoring the polynomial ##a^6-a## is the next thing to do. After that, it becomes clear that ##2\,|\,a^6-6## in any case, as ##a(a-1)\,|\,a^6-a##. So, we are left with what @Infrared has said, the divisor ##3##. We have that ##3## divides ##a(a-1)## iff ##3\,|\,a \Longleftrightarrow a\equiv 0 \operatorname{mod} 3## or ##3\,|\,(a-1) \Longleftrightarrow a\equiv 1\operatorname{mod} 3## because ##3## is prime. Thus we are left with all numbers ##a \equiv 2 \operatorname{mod} 3##, i.e. ##a=3n+2## and ##6\,|\,a^6-a \Longleftrightarrow 3\,|\,a^4+a^3+a^2+a+1## for those numbers. However, if ##a=3n+2## it is easy to see, that ##a^4+a^3+a^2+a+1 =3m+2## which is never divisible by ##3##.

jedishrfu
Mentor
I see quicker that ##(3n+2)^6 = 3m + 1## (because I can use ##x^6 = (x^2)^3## ) than I see the same for ##a^4+a^3+a^2+a+1 =3m+2##

jedishrfu