• Support PF! Buy your school textbooks, materials and every day products Here!

First time a^d = 1 mod n

  • Thread starter cutesteph
  • Start date
  • #1
63
0

Homework Statement


For any positive integer d and n, find the first integer d such that a^d =1 mod n

Homework 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

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:

Answers and Replies

  • #2
BvU
Science Advisor
Homework Helper
2019 Award
13,017
3,009
For any positive integer d and n, find the first integer d such that a^d =1 mod n
Is d given or is d to be found ? Is a arbitrary ? Or would the exercise have been something along the lines of
For any positive integer a and n, find the first integer d such that a^d =1 mod n
 
  • #3
63
0
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.
 

Related Threads on First time a^d = 1 mod n

Replies
2
Views
1K
  • Last Post
Replies
2
Views
924
Replies
10
Views
2K
  • Last Post
Replies
5
Views
1K
Replies
3
Views
1K
Replies
0
Views
4K
Replies
3
Views
5K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
856
  • Last Post
Replies
4
Views
2K
Top