# Math Help - Proof involving mods

1. ## Proof involving mods

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...

2. Originally Posted by asviola
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...
In my opinion the solution for this is best phrased in terms of group theory. Do you know it?

If not, let $|k|=\min\left\{n:k^n\equiv 1\text{ mod }p\right\}$. Claim that if $k^p=1$ then $p=|k|r$ for some $r\in\mathbb{N}$

Hint:
Spoiler:
Division algorithm

3. 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?

4. Originally Posted by asviola
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?
No. $r=m-1$. For you see if you look at my post $|k|=m-1$. Now apply the division algorithm.

Disclaimer: I am not a number theorist. There may be a MUCH better way to do this.

5. 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?

6. Originally Posted by asviola
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 $k^t\equiv 1\text{ mod }m$ is $m-1$ (you do this). Then, given any $k^{\ell}\equiv1\text{ mod }m$ we have that $\ell=z(m-1)+r$ for some $z\in\mathbb{Z}$ and some $r\in\{0,\cdots,m-2\}$. Thus, $1\equiv k^\ell=k^{z(m-1)+r}=\left(k^{m-1}\right)^z\cdot k^r\equiv k^r\text{ mod }m$. Now, if we assume that $r\ne 0$ then $r$ is a positive number less than $m-1$ such that $k^r\equiv1\text{ mod }m$. But! This contradicts that we proved the smallest positive number that does that is $m-1$. It follows that $r=0$ and so $\ell=z(m-1)+0=z(m-1)$ which is what we wanted.

7. I see now, thanks!