PRIMITIVE ROOTS IN QUADRATIC FIELDS II 5 JOSEPH COHEN 0 0 2 n a Abstract. This paper is continuation of the paper ”Primitive J rootsinquadraticfield”. WeconsiderananalogueofArtin’sprim- 9 itive root conjecture for algebraic numbers which is not a unit in real quadratic fields. Given such an algebraic number, for a ratio- ] T nalprimepwhichisinertinthefieldthemaximalorderoftheunit N modulopisp2 1. AnextensionofArtin’sconjectureisthatthere − . are infinitely many such inert primes for which this order is maxi- h mal. weshowthatforanychoiceof85algebraicnumberssatisfying t a a certain simple restriction, there is at least one of the algebraic m numbers which satisfies the above version of Artin’s conjecture. [ 1 1. Introduction v 0 This paper is continuation of the paper ”Primitive rootsin quadratic 2 field” ([8]). In this paper we considered an analogue of Artin’s prim- 1 1 itive root conjecture for units in real quadratic fields. Given such a 0 nontrivial unit, for any rational prime p which is inert, the maximal 5 order of the unit modulo p is p + 1. An extension of Artin’s conjec- 0 / ture is that there are infinitely many such inert primes for which this h t order is maximal. This is known at present only under the General- a ized Riemann Hypothesis. Unconditionally, we showed that for any m choice of 7 units in different real quadratic fields satisfying a certain : v simple restriction, there is at least one of the units which satisfies the i X above version of Artin’s conjecture. In this paper we want to extend r this result for any algebraic integer modulo inert prime p. we will prove a Theorem 1.1. Let K = Q(√∆) be a quadratic field and α 85 be a { i}i=1 set of 85 integers of K such that (1) The norms N(α ) = α σ(α ), of the α′s, are multiplicatively in- i i i i dependent. Date: February 1, 2008. In partial fulfillment for the Ph.D. degree. Supported by grants from the Technion-IsraelInstitute of Technology. 1 2 JOSEPH COHEN (2) 5N(α )∆, N(α ) are not perfect squares. i i (3) M(α ) = σ(α )/α are multiplicatively independent. i i i Then at least one of the 85 integers has at least order p2−1 mod p 24 for infinitely many inert primes p in K. Notethatinthecaseofsplit primes, Narkiewicz ([12])provedamuch stronger result. Since in our case the order is p2 1, which is not “linear”, some of − their divisors are too big and we cannot use the method of [6]. But since p2 1 = (p 1)(p + 1) can be factored into two linear factors, − − with the following remark we can still use the method of [6] Remark 1.2. Consider an algebraic number α in K = Q(√∆). Let p ∤ α be an inert prime in K. Since (1) M(α) αp−1 (mod (p)), ≡ (2) N(α) αp+1 (mod (p)), ≡ we have: ord(M(α)) ord(α) (mod (p)) and ord(N(α)) ord(α) (mod (p)) | | In addition: ord(M(α)) p+1 and ord(N(α)) p 1 | | − But, (p−1,p+1) = 1 or (p 1, p+1) = 1. 2 − 2 So, ord(M(α))ord(N(α)) 2ord(α) (mod (p)) | Let e and e be some integers. If we prove that M(α) and N(α) 1 2 have simultaneously at least orders p+1 and p−1, respectively, then we e1 e2 will obtain that α has at least order p2−1. This way we reduce the 2e1e2 problem to a “linear” problem. PRIMITIVE ROOTS IN QUADRATIC FIELDS II 3 1.1. Notationand Preliminaries. Letπ(y;m,s)thenumberofprimes p y such that p s (mod m) where m and s are some integers, and ≤ ≡ Li(y) E(y;m,s) := π(y;m,s) − ϕ(m) where Li(y) = y dt . Also set R 2 logt E(x;m) := max max E(y;m,s) . 1≤y≤x (s,m)=1| | Denote = p2 1 p x,p u (mod v) where u, v are some A { − | ≤ ≡ } given integers such that (u,v) = 1, and take X = Li(x). ϕ(v) For a square-free integer d, (d,v) = 1, denote := a : a 0 mod d d |A | |{ ∈ A ≡ }| = p2 1 : p x, p umodv, p2 1 0 mod d |{ − ≤ ≡ − ≡ }| d = X p p x,p umodv, p m mod d |{ | ≤ ≡ ≡ }| m=1 m2−1≡0modd d = X p p x,p u mod v, p m mod d |{ | ≤ ≡ ≡ }| m=1 m2−1≡0 mod d (m,d)=1 By the Chinese Remainder Theorem, for each m there exists an integer l such that m d d = X p p x, p lm (mod dv) ; |A | |{ | ≤ ≡ }| m=1 m2−1≡0 mod d (m,d)=1 Since p p x, p l (mod dv) is asymptotically independent m |{ | ≤ ≡ }| of m, there exists some integer l such that d d = π(x;dv,l) X 1 = π(x;dv,l)ρ(d) |A | m=1 m2−1≡0 mod d (m,d)=1 4 JOSEPH COHEN d where ρ(d) = 1. P m=1 m2−1≡0 mod d (m,d)=1 We note that ρ(q) = 2 for any prime q, and hence for any square-free d, ρ(d) = 2ν(d) where ν(d) denotes the number of prime divisors of d. By the definition of E(x;dv,l), ρ(d) Lix 2ν(d) = +ρ(d)E(x;dv,l)) = X +2ν(d)E(x;dv,l). d |A | ϕ(d)ϕ(v) ϕ(d) For any prime q define ω(q) := 2q , ω(d) = ω(q) = 2ν(d)d and ϕ(q) Q ϕ(d) q|d ω(d) R := X = 2ν(d)E(x;dv,l) d d |A |− d Finally, we define the Mo¨bius function, µ(1) = 1 and for a square-free d = p p , µ(d) = ( 1)k. 1 k ··· − Now we want to prove two lemmas. Lemma 1.3. For any prime q > 3 which is relatively prime to v we have: 2 1 (1.1) 0 . ≤ q 1 ≤ 2 − 2 z (1.2) X logq 2log = O(1) (2 w z) q 1 − w ≤ ≤ w≤q<z − where O does not depend on z or w. 2 1 (1.3) Y (1 ) . − q 1 ≫ log2z 2<q<z − q∤v Proof. Since q > 3, it is clear that (1.1) holds. Asforthesecondequality, 2 logq = 2 logq q = 2 logq(1+ P q−1 P q q−1 P q w≤q<z w≤q<z w≤q<z 1 ) = 2 logq + 2 logq = 2log z + O(1) ( logp = q−1 P q P q(q−1) w P p w≤q<z w≤q<z p<x logx+O(1)). PRIMITIVE ROOTS IN QUADRATIC FIELDS II 5 Hence we get (1.2). Finally, 2 2 Y (1 ) Y (1 ) − q 1 ≫ − q 1 2<q<z − 2<q<z − q∤v 2 = exp(log Y (1 )) − q 1 2<q<z − 2 = exp( X log(1 )) − q 1 2<q<z − 2 4 exp( X ( )) ≫ −q 1 − (q 1)2 2<q<z − − Since 2 2 2 2 2 = + + q 1 q q(q 1) ≤ q (q 1)2 − − − and 2 converges, we get P (q−1)2 2<q<z 2 2 Y (1 ) exp( X ) − q 1 ≫ − q 2<q<z − 2<q<z Since 2 X 2loglogz q ∼ 2<q<z we have 2 1 exp( X ) exp( 2loglogz) = − q ≫ − log2z 2<q<z (cid:3) Lemma 1.4. For any square-free natural number d, (d,v) = 1, and a real number A > 0, there exist constants c ( 1) and c ( 1) such that 2 3 ≥ ≥ X (1.4) X µ2(d)3ν(d)|Rd| ≤ c3logAX, (X ≥ 2) 1 d<(loXgx2)c2 Proof. Denote by S the term which we need to estimate. R SR = X µ2(d)3ν(d) Rd | | 1 d<(loXgx2)c2 6 JOSEPH COHEN By the definitions of R and E(x;dv) d SR X µ2(d)6ν(d) E(x;dv) . ≤ | | 1 d<(loXgx2)c2 Since E(x;dv) x if d x, we get that ≪ dv ≤ v µ2(d)6ν(d) 1 1 SR ≪ x2 X d1 |E(x;dv)|2. 2 1 d<(loXgx2)c2 By Cauchy’s Inequality, µ2(d)62ν(d) 1 1 1 SR x2( X )2( X E(x;dv) )2. ≪ d | | 1 1 d<X2 dv<(lovgXx2)c2 For sufficiently large x we obtain µ2(d)62ν(d) 1 1 1 SR x2(X )2( X E(x;dv) )2. ≪ d | | 1 1 d<x2 dv<(logxx2)c2 With Bombieri-Vinogradov Theorem [2] (given any positive con- stant e , there exists a positive constant e such that E(x;d) = 1 2 P 1 d<logxe22x O( x )) for the last sum and the inequality µ2(d)36ν(d) (logw+ loge1x P d ≤ d<w 1)36, [5], p.115, equation (6.7)) we find that for given constant B there exists c such that 2 x S . R ≪ logBx So, for given A there exists c such that 2 X S R ≪ logAX where depends on v and c . (cid:3) 2 ≪ 1.2. Proof of Theorem 1.1 – the sieve part. In this section we use the Selberg lower bound sieve and show that there is some small real number δ and some constant c(δ ) > 0 (which depends on δ ) such 1 1 1 that for at least c(δ ) x primes p x, p u (mod v), if q p2 1 1 log3x ≤ ≡ | − then either q > x1/8+δ1 or q v. | PRIMITIVE ROOTS IN QUADRATIC FIELDS II 7 Now, define S( ,z,v) = a a ,(a, p) = 1 and define a Q A |{ | ∈ A }| p<z p∤v function g by g(t ) = 1,t = 4.42 and g(t) < 1 for t > t . Then (see [5, 0 0 0 Theorem 7.4, page 219]): Lemma 1.5. We have ω(q) logX (loglog3X)8 (1.5) S( ,z,v) XY(1 ) 1 g( )+O( ) A ≥ − q { − 2logz logX } q<z q∤v where the O-term does not depend on X or on z. By Lemmas 1.3 and 1.4, (1.1), (1.2) and (1.4) hold. Hence we can use Lemma 1.3 with z = X18+δ0 2 1 logX (loglog3X)8 S( ,X81+δ0,v) X Y (1 ) 1 g( )+O( ) . A ≥ −q 1 { − 2logX18+δ0 logX } q<X81+δ0 − q∤v By Lemma 1.3 (1.3) we have for δ sufficiently small 0 X x S( ,X81+δ0,v) A ≫ log2X ≫ log3x Thus for such δ we obtain that there is a constant c(δ ) > 0 (which 0 0 depends on δ ) such that for at least c(δ ) x primes p x, p 0 0 log3x ≤ ≡ u (mod v) if q p2 1 then either q > x1/8+δ0 or q v. Hence we obtain | − | that for all 0 < δ < δ there is a constant c(δ ) > 0 (which depends 1 0 1 on δ ) such that for at least c(δ ) x primes p x, p u (mod v), 1 1 log3x ≤ ≡ if q p2 1 then either q > x1/8+δ1 or q v. | − | 1.3. Proof of Theorem 1.1 – The algebraic part. 1.3.1. Construction of the arithmetic sequence. Let K = Q(√∆) be any quadratic field, the integers ring of K, α any algebraic O ∈ O integer and a = N(α). In this section we want to construct integers u and v, (u,v) = 1 such that for all primes p such that p u (mod v), ≡ the discriminant ∆ of Q(√∆) and a satisfy ∆ a ( ) = ( ) = 1. p p − This means that p is inert and a is not a quadratic residue (mod p). In addition we want to obtain by the construction that (p2−1,v) = 1 24 (since after sieving the small factors of p2−1 we may be left with small 24 factors which divide v, see previous section). 8 JOSEPH COHEN Inordertofulfillthesedemands, wewillfirstshowthatthereexist in- finitely many primes p satisfying the following simultaneous conditions (1.6) (−1) = (5) = (a) = (∆) = 1. p p p p − This condition is equivalent to the condition: 1 5 a ∆ B(p) = (1 (− ))(1 ( ))(1 ( ))(1 ( )) = 0 − p − p − p − p 6 Since the Legendre symbol is a multiplicative function, we obtain, 1 a ∆ a∆ 5 5a 5∆ 5a∆ (1 (− ))(1 ( ) ( )+( ) ( )+( )+( ) ( )). − p − p − p p − p p p − p Let S be the set of all integers of the form n = ( 1)b05b1ab2∆b3, b i − ∈ 0,1 . Then { } (1.7) B(p) = ( 1)b0+b1+b2+b3 (n), b 0,1 . P P − P p i ∈ { } p≤Z n∈S p≤Z By the assumption in the theorem each n S is not a perfect square ∈ 3 when b is odd. P i i=0 This assumption, together with the fact that for n not a perfect square (by the reciprocity law for Legendre symbol) (n) = o(π(Z)) as Z P p → ∞ p≤Z implies that B(p) is asymptotic to at least π(Z) (since all the neg- P p≤Z ative summands contribute o(π(Z)) and at least the natural number 1 contributes π(Z)). This shows that the simultaneous conditions have infinitely many solutions p. We fix some particular p satisfying the condition (1.6) and for each 0 odd prime l = 3, such that l 24a∆, we define u = p if l ∤ p2 1, and 6 | l 0 0 − u = 9p otherwise. l 0 Claim 1.6. l ∤ u2 1. l − Proof. If u = p then by the assumption l ∤ p2 1, so l ∤ u2 1. l 0 0 − l − If u = 9p , assume, by reductio ad absurdum, that l u2 1. Hence l 0 | l − l 81p2 1. Since, l p2 1, we obtain that l 80p2. On the other | 0 − | 0 − | 0 hand, by our condition, ( 5 ) = 1 so (p0) = 1 (p 1 (mod 4)). p0 − 5 − 0 ≡ Hence p 2 or 3 (mod 5). Since l p2 1 and p 2 or 3 (mod 5) 0 ≡ | 0 − 0 ≡ we conclude that l ∤ 5. Using the assumption that l p2 1 we deduce | 0− that l = p (if l = p then l ∤ p2 1). Hence (l = 2,3) l ∤ 80p2, which 6 0 0 0 − 6 0 (cid:3) is a contradiction. PRIMITIVE ROOTS IN QUADRATIC FIELDS II 9 In addition let u = p if 8 p 2 1 and u = p 8 if 16 p 2 1. 2 0 0 2 0 0 | − − | − Likewise we take u = p if 3 p 2 1 and u = p 3 if 9 p 2 1. 3 0 0 3 0 0 | − − | − Let v = 24a∆ and u be the common solution of u u (mod 16), 2 ≡ u u (mod 9) and all the congruences u u (mod l). Such a solu- 3 l ≡ ≡ tion exists, by the Chinese Remainder Theorem. Since l ∤ u2 1 for every odd prime l = 2,3, l v, and by the con- − 6 | struction (u2−1,6) = 1 we conclude that (u2−1,v) = 1. 24 24 Finally, if p u (mod v), then p p (mod 24) and p p or 0 0 ≡ ≡ ≡ 4p (mod l) for all odd primes l v. So, (∆) = (∆) = 1, and similarly 0 | p p0 − for a. This completes the construction of u and v. Note that by the construction of the integers u and v we have that (u,v) = 1. (take l an odd prime number, l v = 24a∆ and assume | that l u. Since u u (mod l), l u . Hence l p or 9p (in this l l 0 0 | ≡ | | case l = 2,3). In other words l = p . But p ∤ 24a∆ (p fulfills the 0 0 0 6 simultaneous condition (1.6)) and l 24a∆). | 1.3.2. The last step of the proof. As we saw at the previous subsec- tions, for at least c(δ ) x primes p x, p u (mod v), if q p2 1 1 log3x ≤ ≡ | − then q > x1/8+δ1 or q v. Since (p2−1,v) = 1, if q p2−1 then q > x1/8+δ1. | 24 | 24 Since by the construction of u and v, p 1 (mod 4) and (p2−1,v) = ≡ 24 1, we have that p−1 and p+1 are odd. In addition if p 1 (mod 3) 4 2 ≡ then (p−1,v) = 1 and if p 1 (mod 3) then (p+1,v) = 1 12 ≡ − 6 If we conclude the result about p 1 and p+1 we have for at least − c (δ ) x primes p x, p u (mod v), if q p−1 or q p+1 then 1 1 log3x ≤ ≡ | d− | d+ q > x1/8+δ1, where d = 4 or 12 and d = 6 or 2, respectively. − + For the last step of the proof we need to use a version of Lemma 4 from Narkiewicz [12], which generalized Lemma 2 in [3]. Lemma 1.7. Ifa ,...a are multiplicativelyindependentalgebraicnum- 1 k bers of an algebraic number-field K, G the subgroup of K⋆ generated by a ,...a , and for any prime ideal P not dividing a , a we denote 1 k 1 k ··· by GP the reduction of G (modP), then for all positive y one can have GP < y for at most O(y1+k1) prime ideals P, with the implied constant | | being dependent on the a ’s and K. i 10 JOSEPH COHEN Proof. According to [12], For any real number T denote by M = M(T) the set of all k-element sequences (r ,...,r ) of non-negative integers satisfying 1 k r + r +...+ r T 1 2 k | | | | | | ≤ It is easy to see that for T tending to infinity M(T) = (c+o(1))Tk | | with suitable positive constant c = c . If now P is a prime ideal for k which G < y, then select T to be the smallest rational integer with P | | cTk > 2y and let a = bi for i = 1,...,k. There exist two distinct i ci sequences Z = (z ), W = (w ) in M(T) for which i i bz1 bzk bw1 bwk P 1 ··· k 1 ··· k |cz1 czk − bw1 cwk 1 ··· k 1 ··· k Hence for sufficient large P (since the a′s are multiplicatively inde- i pendent). bz1 bzk bw1 bwk P 1 ··· k − 1 ··· k = D = 0 | c[z1,w1] c[zk,wk] 6 1 ··· k Thus for sufficient large P ν (Πazi−wi 1) 0 P i − ≥ where ν denotes the P-adic valuation and it follows that for fixed P z w ,...,z w we obtain log(max a¯ 2T) T possibilities for 1 1 k k j j − − ≪ | | ≪ P. Finally we obtain P GP < y T1+k y1+k1 |{ | | | }| ≪ ≪ (cid:3) Look at the p 1 case (the case of p + 1 is similar). We have − for at least c (δ ) x primes p x, p u (mod v) such that 1 1 log3x ≤ ≡ if q p−1 then q > x1/8+δ1 where d = 4 or 12. Let p 1 = | d− − − d q (p)q (p) q (p), q (p) > q (p) > ... > q (p), m 7, and − 1 2 m m m−1 1 · · · ≤ let a be some integer where a¯ its image in F∗. p Denote by S the set S = a ,...,a where a ,...,a aremultiplica- n n 1 n 1 n { } tively independent integers and take seven integers a ,...,a from S i1 i7 n and assume that at least one prime, say q (p), which is greater than 1 x1/8+δ1, divides [F∗ : a¯ ] for k = 1,...,7. p h iki