# modulo and congruence classes

• Jan 3rd 2008, 01:39 PM
yellow4321
modulo and congruence classes
.

>
• Jan 3rd 2008, 01:58 PM
ThePerfectHacker
Quote:

Originally Posted by yellow4321
how could i use fermats little theorem on 5^72(mod73) provided my calculator cannot have output of greater than 200. if i used say (5^8)^9 (mod72) id be here forever.

start of like 5^72 congruent to 1 mod 73 ??i guess

2.) how would i calculate the inverse of [5] (subscript/base 27) in Z/27 (Z-intergers)

id want to end up with 1mod27 i think just need help getting there.

Are you asking for a proof of Fermat's little theorem?
• Jan 3rd 2008, 02:37 PM
JaneBennet
Quote:

Originally Posted by yellow4321
2.) how would i calculate the inverse of [5] (subscript/base 27) in Z/27 (Z-intergers)

id want to end up with 1mod27 i think just need help getting there.

You want to find an integer n such that 5n leaves a remainder 1 when divided by 27. Well, 5 times any integer ends in 0 or 5. So just find a multiple of 27 that ends in 4 or 9, and add 1 to it. 27 × 2 = 54; 54 + 1 = 55 = 5 × 11. So the multiplicative inverse of 5 in \$\displaystyle \mathbb{Z}_{27}\$ is 11.