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

Proof Two Primitive Root Conditions Are Equivalent

  • Thread starter golmschenk
  • Start date
  • #1
36
0

Homework Statement


Let n be a nonzero integer and let a be an integer with gcd(a, n) = 1. We have two equivalent conditions which characterize primitive roots:
(i) a is primitive modulo n if the order of a is [tex]\phi[/tex](n).
(ii) a is primitive modulo n if for every element b with gcd(b, n) = 1 we have b [tex]\equiv[/tex] a[tex]^{j}[/tex] mod n for some nonnegative integer j.
Write out the complete proof that condition (i) implies condition (ii). To do this, show first that the integers a[tex]^{0}[/tex], a[tex]^{1}[/tex],..., a[tex]^{\phi(n)-1}[/tex] must lie in distinct congruence classes modulo n. Then explain why this implies condition (ii).

2. The attempt at a solution
I'm trying to figure out how to do the first part of showing that a[tex]^{0}[/tex], a[tex]^{1}[/tex],..., a[tex]^{\phi(n)-1}[/tex] must lie in distinct congruence classes modulo n. I realize that because the numbers are relatively prime has to do something with it. How is the a number taken to a power related to a number it's relatively prime to? I don't necessarily even want the full answer for the question, just more a push in the right direction. I guess of course the full answer wouldn't be bad either though. Maybe with spoiler tags around it would be good? Thanks!
 

Answers and Replies

  • #2
336
0
Let n be a nonzero integer and let a be an integer with gcd(a, n) = 1. We have two equivalent conditions which characterize primitive roots:
(i) a is primitive modulo n if the order of a is [tex]\phi[/tex](n).
(ii) a is primitive modulo n if for every element b with gcd(b, n) = 1 we have b [tex]\equiv[/tex] a[tex]^{j}[/tex] mod n for some nonnegative integer j.
If the order of a is k=[tex]\phi[/tex](n), {a[tex]^{i}[/tex] | i=1,2,..,k} is a reduced residue system mod n. If gcd(b, n) = 1 , b is congruent to some element in the
reduced residue system mod n & hence to a power of a.
 
  • #3
36
0
If the order of a is k=[tex]\phi[/tex](n), {a[tex]^{i}[/tex] | i=1,2,..,k} is a reduced residue system mod n.
Why? Thanks!
 

Related Threads on Proof Two Primitive Root Conditions Are Equivalent

  • Last Post
Replies
1
Views
963
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
9
Views
5K
  • Last Post
Replies
3
Views
636
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
439
  • Last Post
Replies
2
Views
801
  • Last Post
Replies
1
Views
849
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
Top