Problems & Puzzles:
Conjectures
Conjecture 70. n & n+1
primitive roots
Emmanuel Vantieghem sent the
following conjecture:
If p is a prime number > 7, then there
exist an integer n such that n and n+1 both are
primitive roots modulo p.
I have verified the truth of that statement
for all p less than the 20000000th prime.
Examples : (consecutive numbers that are
primitive roots are underlined)
p = 7 ; the primitive roots (mod 7) are 3 ,5
p = 11 ; the primitive roots (mod 11) are
2, 6, 7, 8
p = 13 ; the primitive roots (mod 13) are
2, 6, 7, 11
p = 17 ; the primitive roots (mod 17) are
3, 5, 6, 7, 10, 11, 12, 14
p = 19 ; the primitive roots (mod 19) are 2,
3, 10, 13, 14, 15
p = 23 ; the primitive roots (mod 23) are 5, 7, 10, 11, 14, 15,
17, 19, 20, 21
p = 29 ; the primitive roots (mod 29) are 2,
3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
Q1. Can you probe
this conjecture of find a counterexample?
Jan van Delden wrote:
Just a small observation:
x is a primitive root
modulo p: x^a=1 mod p if and only if a=phi(p)=p1. Or to put it
differently the order of x mod p is maximal.
Furthermore the order of a general x mod p is a divisor of p1.
Now (x+1)^a mod p = sum
(x^b C(a,b) mod p, b=0..a) with C(a,b) the number of combinations
(binomium of Newton).
I see no fast way to
reduce such an expression to a simple form, what’s worse, the terms
(x+1)^a mod p will in general be different from x^a mod p.
However a simple case
would be considering x and px:
(px)^a mod p = (1)^a
*x^a mod p:
= x^a mod p if a is even
= –x^a mod p if a is odd
Choose p such that we have
px=x+1: p=2x+1, i.e. x=(p1)/2 and x+1=(p+1)/2, let’s suppose x is
a primitive root mod p.
We have (x+1)^a = x^a both
unequal to 1 mod p if a(p1) and a even, both equal to 1 mod p if
a=p1, because x is a primitive root mod p.
We therefore need x^a<>1
mod p, for all odd a(p1) or for all odd ax which is the same
thing.
We always have x^x=1 mod
p (if x is a primitive root mod p). So we should at least have that
this a is a proper divisor of x, or in other words that x has
another divisor 2. Hence p=1 mod 4 is necessary. It is also
sufficient because if x^a=1 mod p with a<=x/2, then x^(2a)=1 mod p
but 2a<=x<p1 in contradiction with x being a primitive root.
If p=1 mod 4 and x=(p1)/2
is a primitive root mod p then x and x+1 are primitive roots mod p.
p=5,13,29,37,53,61,101,149,173,181,197,269,..
Maybe some similar
observations can be made for other situations.
Emmanuel wrote:
Immediately after the appearance of this conjecture, W. Edwin Clark sent
me a mail to tell me that, by a theorem of M. Szalay, the conjecture is
true for all primes p >
10^19 (M. Szalay, On the distribution of the primitive roots of a prime.
Journal of Number Theory 7 (1975), 184188). So,
there remains only a finite number of primes to be checked by hand. However,
I do not believe that this can be done in reasonable time.
For
some primes, it is possible to prove the conjecture. For
instance, if p is
of the form 2q+1, q prime >
5. The number of primitive
roots modulo p is then precisely q1. If
we take q1 numbers
between 2 and p2 with
minimal consecutive distances > 1, we should have to choose 4 or 9 among
them. But these are not
primitive roots.
There
is a similar but stronger result of E. Vegh, that confirms the
conjecture for primes p such
that phi(p1)/(p1) > 1/4,
phi() being Eulers totient function (E.
Vegh, A note on the distribution of the primitive roots of a prime, J
of Number Theory, 3 (1971),
1318).
Here is
a heuristic argument for the conjecture :
Assume p prime
(not too small) and take ad
random j = phi(p1) integers r(i) such
that 1 < r(1)
< r(2) < ... < r(j) < p1. Then,
on the average, the frequency table for the differences r(i+1)r(i) shows
a remarkable maximum at the beginning, i. e. : the equality r(i+1)r(i)
= 1 occurs most often. Now,
if g is
a primitive root mod p, then it is well known (and used sometimes by
computer simulation of randomness !) that the sequence g^1,
g^2, ... ,g^(p1) modulo p behaves as if it was chosen ad random. So,
if we restrict ourselves to powers of g that
are relatively prime to p1,
we get the sequence of primitive roots modulo p. So,
that sequence can be considered as a random one, and thus ...
Actually, the number of differences 1 for
the primitive roots seems to be much greater than the differences 1 for
random sequences, but that may be coincidence. Anyhow,
the fact that the conjecture is true for p
> 10^19 shows that the
heuristic argument is not entirely phantasy (at least, I hope so).
***
