Assume m is prime and a is some integer between 0 and m-1, prove there exists some positive integer r, such that a^t ≡ 1(mod m) if and only if t=nr, n=0,1,2,3,...
I started this proof by first noting that m divides (a^t - 1) from the definition of modulus, and therefore (a^t-1)=km where k exists in the set of positive ints. Then I added 1 to both sides, a^t=km+1 and took the log to get t*log(a)=log(km+1) --> t=rn so this is rn*log(a)=log(km+1),
therefore r=log(km+1)/(n*log(a)) --> r=log(km+1-a)/n but, I'm not sure where to go from here, or if I'm even headed in the right direction...
I haven't learned about group theory, but could Fermat's Theorem apply here?
a^(p-1)≡1(mod p) where p is prime, so if t = p-1, then nr=m-1 (based on the given equation from the original problem), so r=(m-1)/n, and r will be a positive int for at least n=1, right?
Maybe I'm just stupid, or tired, but I don't see how you get abs(k)=m-1, I also don't understand why you claim k^p=1, because that implies p=0. And when I go to do the division algorithm I'm getting confused because there are so many variables in this problem, so the division algorithm takes in an integer a and a positive integer d then continually subtracts d from a until it's less than d and outputs q=a div d and r=a mod d. So, the input a = 1 and d = m?
Ok. I'll show you this trick once. If you can prove that the smallest positive number such that is (you do this). Then, given any we have that for some and some . Thus, . Now, if we assume that then is a positive number less than such that . But! This contradicts that we proved the smallest positive number that does that is . It follows that and so which is what we wanted.