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.
Hi,
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)
or
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.
Well, $\displaystyle 2^4 = 16 $ and what is $\displaystyle 16 $ modulo $\displaystyle 31 $?
For the other problem, first observe that $\displaystyle 2^{23}\equiv 1 \mod{47} $.
This is because $\displaystyle 2^{23} = 2^6\cdot 2^6\cdot 2^6\cdot 2^5 $.
$\displaystyle 2^6=64\equiv 17 \mod{47} $, So $\displaystyle 2^{23}\equiv 17\cdot 17 \cdot 17 \cdot 32 \mod{47} $
$\displaystyle \equiv 7\cdot 17\cdot 32 \mod{47} $
$\displaystyle \equiv 25\cdot 32 \mod{47} $
$\displaystyle \equiv 1 \mod{47} $
Now $\displaystyle 2222 = 96\cdot 23+14 $
so $\displaystyle 2^{2222} = 2^{96\cdot 23+14} = \left(2^{23}\right)^{96}\cdot 2^{14} \equiv 1^{96}\cdot 2^{14} =2^{14} \mod{47} $.
$\displaystyle 2^{14} = \left(2^7\right)^2 = 128^2\equiv (-13)^2 \equiv 28 \mod{47} $