Author |
Topic: Upper bound on a product having primitive root (Read 2625 times) |
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
 |
Upper bound on a product having primitive root
« on: Dec 8th, 2011, 3:41pm » |
 Quote  Modify
|
Prove that if ab has a primitive root with (a,b) = 1 then a < 3 or b < 3 .
|
| « Last Edit: Dec 8th, 2011, 3:42pm by Michael Dagg » |
 IP Logged |
Regards,
Michael Dagg
|
|
|
peoplepower
Junior Member
Posts: 63
|
|
Re: Upper bound on a product having primitive root
« Reply #1 on: Aug 13th, 2012, 5:10pm » |
Quote Modify
|
I think I've got it, though the solution is probably not as neat as the best proof.
(Let o(n) refer to the the totient of n.)
Let G be the group of residue classes of the integers modulo ab. Assume it is cyclic with generator c.
Define A to be the product of all primes p|ab, and A' to be the product over the primes p|ab of factors (p-1).
(*)Note that ab-o(ab) =o(ab)/A'.
We start off with a homomorphism f from G into the multiplicative group H=(Z/AZ)x, given by the mapping of x to its residue class modulo A. Since f is just a changing of representation on the elements of G less than A, we see that f is surjective. (The implicit ordering on G is given by the ordering of the natural representatives of the elements of G.)
Therefore, H is cyclic of order A'. Furthermore, because of (*), A-A'=1. Rewrite it as follows, where q is the largest prime dividing ab,
qA/q-qA'/(q-1)+A'/(q-1)=1.
Then, A'/(q-1)=  p<q(p-1) = 1 (mod q). The product on the left cannot have any factors greater than (2-1), which means that it is a product of at most one factor. It follows that A is either q or 2q. Without loss of generality, a=2n and b=qm.
If n is 0 or 1, then we are done, so assume n>1.
Let Gm,n denote the multiplicative group of congruence classes of the integers modulo 2nqm.
This next paragraph is bonus:
In the case m=0, we use induction on n, starting with n=3, which has a trivial image under the homomorphism mapping x to x2. Given that Gm,n is not cyclic, the group after incrementing n, Gm,n+1 will also not be cyclic. We can see that because Gm/<-1> does not have a generator.
(It is worth mentioning that G0,2 is cyclic, generated by -1.)
From now on assume m>0. Let k=2nqm. Notice that k/2+1 is relatively prime to both 2 (and so 2n) and q (and qm). The square of k/2+1 is 22(n-1)q2m+k+1, which is congruent to 1 modulo k. Additionally, k-1 is a square root of 1. If these two square roots of unity were equal, then k=4, contradicting the hypothesis on m.
G=Gm,n has two distinct square roots of 1. Therefore, G does not possess a generator, since if c were to generate it, then cx=k/2+1 and cy=k-1 with x and y both smaller than o(k). However, 1=c2x=c2y, implying that x = y = o(k)/2.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print