Modular arithmetic

  • I
  • Thread starter rashida564
  • Start date
  • #1
rashida564
Gold Member
220
6

Summary:

Find a ∈ Z such that a^6 ≡ a mod 6

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
12,533
8,950
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\,.##
 
  • #3
rashida564
Gold Member
220
6
Is it try and error method?
 
  • #4
Infrared
Science Advisor
Gold Member
477
181
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##.
 
  • #5
12,533
8,950
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##.
 
  • #6
33,925
9,648
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##
 

Related Threads for: Modular arithmetic

  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
963
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
1
Views
479
  • Last Post
Replies
3
Views
2K
Top