Modular arithmetic and exponents

[miren324]

I have a homework problem and I use a rule to solve it that seems to be true, at least for small numbers, but I cannot seem to find a clearly stated theorem assuring me that it is true.

Here's the problem with my solution:

Find the remainder of the division of 2^(36!) by 37.

Proof: By Wilson's Theorem, 36! = -1 (mod 37) = 36 (mod 37). Then 2^(36!) = 2^36 (mod 37). By Fermat's Little Theorem, 2^36 = 1 (mod 37). Thus, the remainder of the division of 2^(36!) by 37 is 1.

So the rule that I can't seem to find a clearly stated theorem for is "If b = k (mod p) with p prime, then a^b = a^k (mod p)." Not sure if the prime restriction is necessary. Maybe there's a more general rule I'm forgetting, or maybe my solution is completely wrong. I don't know.

 

[lippyka]

The theorem you are looking for is called Euler's Theorem. It states that: If a and n are coprime integers, then a^φ(n) ≡ 1 (mod n), where φ(n) is Euler's totient function. For your specific case, since 37 is prime, φ(37) = 36. Thus, Euler's theorem states that a^36 ≡ 1 (mod 37).