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



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 previous question i just asked.
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.



