Results 1 to 3 of 3

Thread: 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 $\displaystyle x^k \equiv a \ (mod \ n) $ has a solution, then $\displaystyle a^{ \phi / d } \equiv 1 \ (mod \ n) $, where d = gcd ( $\displaystyle \phi (n) , k $ ).

    Note: $\displaystyle \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 $\displaystyle 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