Results 1 to 7 of 7

Math Help - Proof involving mods

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    8

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by asviola View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    8
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by asviola View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    8
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by asviola View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2010
    Posts
    8
    I see now, thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mods Help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 27th 2010, 12:38 AM
  2. mods
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 23rd 2010, 04:08 AM
  3. Mods.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 28th 2009, 02:47 AM
  4. proof: mods and number theory
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 20th 2008, 06:11 PM
  5. Mods
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 24th 2007, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum