# Thread: find the least positive residue

1. ## find the least positive residue

Find the least positive residue of 2^2004 modulo 31

2. Originally Posted by mandy123
Find the least positive residue of 2^2004 modulo 31
$2^5 \equiv 1(\bmod 31)$ so $2^{2000} \equiv 1^{400} =1 (\bmod 31)$. Thus, that is $2^{2004} \equiv 2^{4} = 16(\bmod 31)$.

3. 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.

4. Originally Posted by carabidus
...
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^14 = 28 mod 47

So, 28 is the least positive residue mod 47 of 2^2222.
$2^{2222} \equiv 28 \mod 47$

5. ## Question on least positive residule

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.

6. Originally Posted by nush
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, $2^4 = 16$ and what is $16$ modulo $31$?

For the other problem, first observe that $2^{23}\equiv 1 \mod{47}$.
This is because $2^{23} = 2^6\cdot 2^6\cdot 2^6\cdot 2^5$.
$2^6=64\equiv 17 \mod{47}$, So $2^{23}\equiv 17\cdot 17 \cdot 17 \cdot 32 \mod{47}$
$\equiv 7\cdot 17\cdot 32 \mod{47}$
$\equiv 25\cdot 32 \mod{47}$
$\equiv 1 \mod{47}$

Now $2222 = 96\cdot 23+14$
so $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}$.

$2^{14} = \left(2^7\right)^2 = 128^2\equiv (-13)^2 \equiv 28 \mod{47}$

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# what is least positive residue

Click on a term to search for related topics.