| Author |
Message |
fullofquestions
Joined: 07 Oct 2007
Posts: 18
|
| Posted: Fri Oct 26, 2007 4:05 pm Post subject: Congruences: What is the remainder when 2^345 is / by 29 |
|
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. |
|
| Back to top |
|
 |
lime
Joined: 04 Dec 2007
Posts: 46
|
| Posted: Mon Feb 04, 2008 5:45 pm Post subject: |
|
I think, my answer might be too late, cause apparently you were preparing for the autumn test. I will try to answer though.
| Quote: | 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)
| Quote: | 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. |
|
| Back to top |
|
|
|
