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.