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

[fullofquestions]

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.

[lime]

I think, my answer might be too late, cause apparently you were preparing for the autumn test. I will try to answer though.

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?

Frankly, when I was reading this book for the first time I got absolutely the same question.
Here was used the property
"If a1==a2 (mod n) and b1==b2 (mod n) then
a1*a2==b1*b2 (mod n)"
Therefore multiplying next two congruences:
1^12==1 (mod 29)
2^9==2^9 (mod 29) (it can be derived from 0==0 (mod 29) by adding 2^9 to both sides)
we get
1^12 * 2^9 == 2^9 (mod 29)

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?

19 comes from the fact that 48=1*29+19. It is actually the quotient when you divide 48 by 29 and can be easily calculated. It is simple!
2^5*2^4==3*2^4 (mod 29) actually also comes from the multiplication property and could be derived by multiplying next two congruences:
2^5==3*2^4 (mod 29)
2^4==2^4 (mod 29)

Also I have discovered for myself that it is very helpful to remember that if:
a==b (mod n)
then
a^m==x (mod n) could be also rewritten as b^m==x (mod n). Or
a^m==b^m==x (mod n)
And this property was actually used here twice.