Continuing to mimic what we did in the prime case we discover that we still have

Question

Continuing to mimic what we did in the prime case we discover that we still have some work to do. We are now justified in saying that the product of all the congruence classes in {5 middot 1, 5 - 2,..., 5 middot 20} is congruent mod 21 to the product of all the congruence classes in {1, 2, 3,..., 20} so that we will get that 5^20 middot 20! simelarly 20!(mod21). The problem is that 20! is not invertible mod 21 so we can't multiply both sides by the multiplicative inverse. Compute 20!(mod21) and note that it is not invertible. (You should see that 5^20 middot 20! similarly 20! (mod 21) is certainly valid but it tells us nothing about 5^20 (mod 21)middot) Most people probably would have given up at this point, but Euler had a great idea. His idea was to only look at the invertible congruence classes. Let's see how this works. There are 12 congruence classes that are invertible mod 21. They are 1, 2, 4. 5. 8.10,11,13, 16. 17. 19, 20. (We call this a reduced residue system mod 21.) If we multiply each of these by 5 and reduce mod 21 we get 5,10, 20, 4, 19, 8,13, 2, 17, 1,11,16 Notice that we now get the same set of 12 equivalence classes but in a different order.

Explanation / Answer

20! is product of integers from 1 to 20 which includes 3 and 7

Hence, 20! is a multiple of 21

Hence,

20!=0 mod 21

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.