### Congruences: What is the remainder when 2^345 is / by 29

Posted:

**Fri Oct 26, 2007 12:05 pm**I don't remember having experience with this but I think these types of problems are easy enough to learn for easy points. Unfortunately, I tried to follow the explanation and there were two steps that I could not figure out where they came from.

Let == be used for the congruence operator (triple horizontal line)

Question:

What is the remainder when 2^345 is / by 29?

In symbolic form this reads like:

2^345 == x (mod 29)

Step 1:

Since 29 is a prime number, Fermat's little theorem states that

2^28 == 1 (mod 29)

Therefore, 2^345 = (2^28 )^12 * 2^9

Step 2:

2^345 = (2^28 )^12 * 2^9 == 1^12 * 2^9 == 2^9 (mod 29)

Where did the 2^9 (mod 29) above just come from. In particular the 2^9?

Step 3:

Since 2^5 == 3 (mod 29), 2^9 = 2^5 * 2^4

2^5 * 2^4 == 3 * 2^4 = 48 == 19 (mod 29) (The answer is 19)

I see that you replace 2^5 with 3. Where did the 19 (mod 29) come from, in particular the 19? Also, why are they using a congruence operator to signify 2^5 * 2^4 is equal to 3 * 2^4?

Any help is greatly appreciated.

Let == be used for the congruence operator (triple horizontal line)

Question:

What is the remainder when 2^345 is / by 29?

In symbolic form this reads like:

2^345 == x (mod 29)

Step 1:

Since 29 is a prime number, Fermat's little theorem states that

2^28 == 1 (mod 29)

Therefore, 2^345 = (2^28 )^12 * 2^9

Step 2:

2^345 = (2^28 )^12 * 2^9 == 1^12 * 2^9 == 2^9 (mod 29)

Where did the 2^9 (mod 29) above just come from. In particular the 2^9?

Step 3:

Since 2^5 == 3 (mod 29), 2^9 = 2^5 * 2^4

2^5 * 2^4 == 3 * 2^4 = 48 == 19 (mod 29) (The answer is 19)

I see that you replace 2^5 with 3. Where did the 19 (mod 29) come from, in particular the 19? Also, why are they using a congruence operator to signify 2^5 * 2^4 is equal to 3 * 2^4?

Any help is greatly appreciated.