Find the least positive residue of 2^2004 modulo 31
I have a similar problem to solve. Let me see if I have this straight in your example before I move on to my problem.
All multiples of 5 in the exponent will be congruent to 1 modulo 31 or in other words:
2^(5k) = 1 mod 31 where k is a positive integer.
When you divide 2004 by 5, you get 4 as a remainder. The remainder is tacked onto the final calculation:
2^4 = 16 mod 31
Here's a similar problem I've been working on: Find the least positive residue mod 47 of 2^2222. Please check my solution:
2^23 = 1 mod 47. Therefore, 2^(23k) = 1 mod 47. Divide 2222 by 23 and I have 14 as a remainder. The final calculation is:
2^14 = 28 mod 47
So, 28 is the least positive residue mod 47 of 2^2222.
I'm trying to understand congruences, and least positive residues in specific. Could someone please explain to me how you get the 16 in
2^4= 16 mod (31)
2^2222= 28 mod (47)
I understand everything until the previous step, but I'm not sure of how you get the 16 and the 28 terms. Thanks in advance.