[seqfan] Definition of primitive root (was Re: changes to A205989)
davidwwilson at comcast.net
Sat Feb 18 23:39:11 CET 2012
To clarify this to other readers:
A205989(n) gives the smallest prime p >= 10^n with primitive root 10.
The question is about the value of a(0). Alois contends that 10 is a
primitive root modulo 2, in which case A205989(0) = 2. I contend that 10
is not a primitive root modulo 2, which implies A205989(0) = 7 (since we
would agree that 10 is not a primitive root modulo 3 or 5).
Alois cites the link below, which essentially defines a primitive root
of prime p as a number whose powers include all residues of p except 0.
The only nonzero residue of 2 is 1, which is covered by 10^0 = 1, so by
this definition, 10 is a primitive root of 2 (in fact, 0 is a primitive
root of 2). Wikipedia gives essentially the same definition which does
not require a primitive root modulo n to belong to the multiplicative
group modulo n, making 10 a primitive root of 2. I contend that both of
these definitions are technically incorrect. I suspect they are
simplifications aimed at less mathematically sophisticated audiences,
and therefore tend to avoid mathematical rigor or deeper subjects like
group theory, and are a bit sloppy on that account.
My understanding is that a primitive root of n is a member of the
multiplicative group modulo n which generates that group. Since 10 is
not coprime to 2, it is not in the multiplicative group of 2, and hence
cannot be a primitive root of 2.
I think MathWorld agrees with me, but I have to pry it out. MathWorld
requires that primitive root r of n be of multiplicative order phi(n)
modulo n, which implies that r^phi(n) == 1 (mod n). For r = 10 and n =
2, we need 10^1 == 1 (mod n), which is not true, so 10 is not a
primitive root of 2 by this definition. Certainly r^phi(n) == 1 (mod n)
implies that r is coprime to n, which puts r in the multiplicative group
modulo n (except when n = 1, another can of worms opened by sloppy
[Aside: MathWorld defines the multiplicative order of b modulo n as "the
smallest exponent of e for which b^e == 1 (mod n)", failing to require b
> 0. This omission forces b modulo n to be identically 0, which can
never equal phi(n), so there is no such thing as a primitive root. This
agrees with my argument that 10 is not a primitive root of 2, but
doesn't inspire confidence in MathWorld as an authority].
I am pretty sure I am right (that a primitive root modulo n must be a
member of the multiplicative group modulo n), but poking about the web
for corroboration has been singularly unrewarding.
So I am going to throw the question to the number theory wizards: Is 10
a primitive root of 2?
Please do me this favor: If you don't know the answer, don't clog the
mailing list with ill-considered conjectures or opinions, there seems to
be enough of them out there already. I don't want this to be a
popularity contest, I want an authoritative answer from an experts or
authoritative text on the subject.
On 2/18/2012 2:32 PM, Online Encyclopedia of Integer Sequences wrote:
> Dear David W. Wilson:
> Alois P. Heinz commented on your changes to A205989:
> I am not convinced that this is correct:
> In my opinion a(0) = 2.
> Visit http://oeis.org/draft/A205989 for the latest revision of A205989.
> Best regards,
> -- The OEIS Wiki
> P. S. REPLIES TO THIS EMAIL WILL BE DISCARDED.
> To reply, please visit the sequence page:
More information about the SeqFan