Results 1 to 3 of 3

Math Help - Phi problem

  1. #1
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2

    Phi problem

    Let a,n be positive integers with gcd(a,n)=1. Show that if x^k \equiv a \ (mod \ n) has a solution, then a^{ \phi / d } \equiv 1 \ (mod \ n) , where d = gcd (  \phi (n) , k ).

    Note:  \phi (a) denotes the number of positive integers less than a that are relative prime to a.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    I think you forgot to mention the important detail. If n has a primitive root ...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2006
    Posts
    705
    Thanks
    2
    I'm reading the problem now and it didn't mention that n has a primitive root, perhaps it is a mistake?
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum