Results 1 to 4 of 4

Math Help - powers and congruences

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    powers and congruences

    Hi, I don't know how to do math code or anything to make it look good, but bear with me please.



    Given integers a and m,
    Suppose a^e == 1 mod m (where == is the congruence sign, ^ raises to a power)
    Suppose e is the smallest positive integer for which this is true.
    If u>0, show that a^u == 1 mod m if and only if e divides u.


    It's easy to show that if e divides u, then a^u == 1 mod m.
    I am having a hard time showing the other direction though.

    One thing I think that might be useful in the proof is to multiply both sides of a^e == 1 mod m by a^(u-e) to obtain a^u == a^(u-e) mod m. If anyone has any hints, please let me know. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by jimmyjimmyjimmy View Post
    Hi, I don't know how to do math code or anything to make it look good, but bear with me please.



    Given integers a and m,
    Suppose a^e == 1 mod m (where == is the congruence sign, ^ raises to a power)
    Suppose e is the smallest positive integer for which this is true.
    If u>0, show that a^u == 1 mod m if and only if e divides u.


    It's easy to show that if e divides u, then a^u == 1 mod m.
    I am having a hard time showing the other direction though.

    One thing I think that might be useful in the proof is to multiply both sides of a^e == 1 mod m by a^(u-e) to obtain a^u == a^(u-e) mod m. If anyone has any hints, please let me know. Thanks.


    Hint: Euclidean algorithm. Divide u by e with residue:  u =xe + r\,,\,\,with\,\,\,r=0\,\,\,or\,\,\,|r|<e

    now raise a to the u=th power and use minimality of e...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    68
    I’m not sure if the Euclidean algorithm works here (but I could be wrong).

    Do you know group theory? The problem is very simple if you consider the multiplicative group \mathbb Z_m^\times of the units of the ring \mathbb Z_m of integers modulo m. Then if e is the smallest positive integer such that a^e\equiv1\pmod m, this means a\in\mathbb Z_m^\times has order e in \mathbb Z_m^\times – and the rest is just group theory.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by proscientia View Post
    Im not sure if the Euclidean algorithm works here (but I could be wrong).

    Do you know group theory? The problem is very simple if you consider the multiplicative group \mathbb Z_m^\times of the units of the ring \mathbb Z_m of integers modulo m. Then if e is the smallest positive integer such that a^e\equiv1\pmod m, this means a\in\mathbb Z_m^\times has order e in \mathbb Z_m^\times and the rest is just group theory.

    u=xe+r \Longrightarrow 1=a^u=a^{xe+r}=\left(a^e\right)^xa^r=a^r \Longrightarrow r=0 by\,\,minimality\,\,of\,\,e\,\,\Longrightarrow e \mid u and we're done, and no group theory at all was needed.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences, Powers, and Euler's Formula
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 23rd 2010, 06:26 PM
  2. Congruences, Powers, and Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: January 22nd 2010, 01:14 AM
  3. Some congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 3rd 2010, 03:42 PM
  4. Congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 7th 2009, 02:26 PM
  5. congruences
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: March 30th 2008, 10:11 AM

Search Tags


/mathhelpforum @mathhelpforum