Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Math Topics » alt.math.undergrad.independent

Topic: Congruences
Replies: 4   Last Post: Nov 7, 1996 12:44 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Scott Phung

Posts: 32
Registered: 12/6/04
Congruences
Posted: Nov 5, 1996 10:42 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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! ]





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.