wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Upper bound on a product having primitive root
        
(Message started by: Michael Dagg on Dec 8^th, 2011, 3:41pm)

Title: Upper bound on a product having primitive root
Post by Michael Dagg on Dec 8^th, 2011, 3:41pm

Prove that if ab has a primitive root with (a,b) = 1 then a < 3 or b < 3 .

Title: Re: Upper bound on a product having primitive root
Post by peoplepower on Aug 13^th, 2012, 5:10pm

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)= http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cpi.gif_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=2ⁿ and b=q^m.

If n is 0 or 1, then we are done, so assume n>1.
Let G_m,n denote the multiplicative group of congruence classes of the integers modulo 2ⁿq^m.

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 x². Given that G_m,n is not cyclic, the group after incrementing n, G_m,n+1 will also not be cyclic. We can see that because G_m/<-1> does not have a generator.
(It is worth mentioning that G_0,2 is cyclic, generated by -1.)

From now on assume m>0. Let k=2ⁿq^m. Notice that k/2+1 is relatively prime to both 2 (and so 2ⁿ) and q (and q^m). The square of k/2+1 is 2^2(n-1)q^2m+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=G_m,n has two distinct square roots of 1. Therefore, G does not possess a generator, since if c were to generate it, then c^x=k/2+1 and c^y=k-1 with x and y both smaller than o(k). However, 1=c^2x=c^2y, implying that x = y = o(k)/2.