Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Scott Phung Posts: 32 Registered: 12/6/04
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! ]

Date Subject Author
11/5/96 Scott Phung
11/6/96 brian tivol
11/6/96 Brian and/or Margo Gordon
11/6/96 Jeremy Aaron Horwitz
11/7/96 Jeremy Aaron Horwitz