# 9 ^ 100 (mod 11) ?

Relevance
• Login to reply the answers • JOHN
Lv 7
1 month agoReport

@Morewood. I know all of that. The idea was to offer something different from the other answers, one that someone who knows no umber theory could understand. I thought I had made that clear in the preamble to my solution.

• Login to reply the answers
• Use Fermat's Little Theorem, and this is trivial:

If p is prime and (a,p) = 1 then a^(p-1) = 1 mod p

11 is a prime, and (9,11) = 1 (i.e., they are relatively prime).

Therefore 9^10 = 1 mod p, and so is 9^100 since 100 is a multiple of 10:

9^(100) = 9^(10)^10 = 1^10 = 1 mod 11

Other solutions are OK, but way more work. If this is from a number theory class, you definitely should be using FLT, which is simple and very basic to number theory. You should also know Euler's extension to this, (a,n) = 1 ==> a^phi(n) = 1 mod n.

• Login to reply the answers
• 9^100 (mod 11)

= (9²)^50 (mod 11)

= 81^50 (mod 11)

= 4^50 (mod 11)

= (2²)^50 (mod 11)

= 2^100 (mod 11)

= (2^5)^20 (mod 11)

= (-1)^20 (mod 11)

= ((-1)²)^10 (mod 11)

= 1^10 (mod 11)

= 1 (mod 11)

1

• Login to reply the answers
• 9 mod11 = 9

9^2 mod11 = 4

9^3 mod 11 = 3

9^4 mod11 = 5

9^5 mod11 = 1

9^6 mod11 = 9

Pattern repeats every fifth term.

100/5 =20 with no remainder

9^100 mod11 = 1

• Login to reply the answers