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: 0

 Scott Phung Posts: 32 Registered: 12/6/04
Congruences
Posted: Nov 7, 1996 12:50 AM

Thanks to the two people (and possibly more after this
message) who sheded light on this subject.

I do get the lessons taught here. Looking up my number
thoery book (it's not too good at providing examples),
i see a more useful function called Euler's generization of
Fermat's function.

First, i would like to ask a question concerning the

5^999,999 = x mod7
5^6 = 1 mod 7
so 5^999,999 = 5^3 * (5^6)^166,666 mod7

But is it alright to replace (5^6) with 1,
and still leave the ^166,666 above the 1?
does this work, in theory, if say 5^6 was
replaced with say n (just imagine it)?

5^999,999 = 5^3 * n^166,666 mod7

ok, now for euler's phi function,
It is the one, a^phi(m) = 1 (mod m)
with gcf of (a, m) = 1

But what if a is a factor of m (a | m) or vice versa?
Do you reduce one or the other? Consider this example.

2^32 = x mod6

what value k for the exponent will make
2^k = 1 mod6?

i don't think we can apply euler's function here, since
2 is a factor of 6.

2^2 = 1 mod3
2^0 = 1 mod2

Thanks,
Scott.