1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

First time a^d = 1 mod n

  1. Jan 31, 2015 #1
    1. The problem statement, all variables and given/known data
    For any positive integer d and n, find the first integer d such that a^d =1 mod n

    2. Relevant equations
    Euler's totient function phi(n) = # of #s relatively prime to n
    Will solve the condition if a and n are coprime but not for the first d
    3. The attempt at a solution
    If a and n are not coprime then there is no solution.
    I am not sure how to find the smallest d such the condition holds. I know that d will be a factor of Euler's totient function.
     
    Last edited by a moderator: Jan 31, 2015
  2. jcsd
  3. Jan 31, 2015 #2

    BvU

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Is d given or is d to be found ? Is a arbitrary ? Or would the exercise have been something along the lines of
     
  4. Jan 31, 2015 #3
    d is to be found. Essentially I want to find the smallest integer d such that a^d = 1 mod n holds true.
    Yes, For any positive integer a and n, find the first integer d such that a^d =1 mod n is how the problem should have been stated.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted