Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Congruences
Posted:
Nov 5, 1996 10:42 PM


Hello, i have a simple question.
[ What's the best way to reduce a congruence? ]
By this, i mean to reduce a really large number to a number, smaller than it's modulus (divisor).
Consider this example brought to you courtesy of Fermat.
What is the remainder upon dividing 5^999,999 by 7?
My way to answer this beast goes like this.
Let c= equal the triple slash congruent sign (like = but with an extra line on top).
So 5^999,999 c= x(mod7)
I proceed with 5^1 c= 2 (mod7)
thus 5^2 c= (2)^2 (mod7) > thus 5^2 c= 4 (mod7)
so (5^2)^4 c= 4^4 (mod 7) > so 5^8 c= 4 (mod7)
so 5^8 * 5 c= 4 * 5 (mod7) > so 5^9 c= 20 c= 6 (mod7)
So 5^9 c= 6 (mod7)
or algebraically, 5^9 = 7k + 6, for some integer k. > 1
<! Now for the nine modulus 7 part
> 9 c= 2 (mod7) > 9^2 c= 4 (mod7)
(9^2)^4 c= 4^4 (mod7) > 9^8 c= 4 (mod7)
9^8 * 9 c= 4 * 9 (mod7) > 9^9 c= 1 (mod7) > 2
So 9^9 = 7k + 1, for some integer k. > 3
Can i substitue this into the first part? I mean can you substitute a number's congruent part if the number is an exponent? I know that this is allowed if the number is a base. (5 in this case)
5^9 c= 5^2 (mod7), since 9 c= 2 (mod7)
5^(9^9) c= 5^(1) (mod7), since from 2, 9^9 c= 1 (mod7)
I believe there is something i could do with the above information, mainly equations 1, 2 and 3 but i'm stuck.
But i could creully go on towards 999,999 with the above method, but it would take terribly long. (Yes i have done it!)
I know for a fact that the answer is 6.
So is there a finish to my solution, or is there a better way to tackle this problem?
Any help would be appreciated, Scott.
> [ Prefer an answer in this newsgroup, so everyone can read it and learn from it! ]



