[seqfan] Definition of primitive root (was Re: changes to A205989)

[David Wilson]

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 
definitions).

[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.

Thanks.

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.
>
> http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html
>
> 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:
> http://oeis.org/draft/A205989
>