Undergrad Modular Arithmetic: Find Multiples, Understand the Reason

[rashida564]

TL;DR

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.

 

[fresh_42]

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\,.$

 

[rashida564]

Is it try and error method?

 

[Infrared]

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$.

 

[fresh_42]

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$.

 

[mfb]

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$