[seqfan] Re: A000108(n) ≡ 1 (mod 6)

[Joerg Arndt]

Henri Cohen, A Course in Computational Algebraic Number Theory, page 26:

Lemma 1.4.5.
Let p be an odd prime, and let g be a primitive root modulo p.
Then either g or g+p is a primitive root modulo every power of p.

So you need to check that 2 is a primitive root of 9
and you are done (Pari/GP):
? znorder(Mod(2,9))
6
? znorder(Mod(2,9))==eulerphi(9)
1

Cohen, same page as above:

Therefore to find a primitive root modulo p^a for p an odd prime and a >= 2,
proceed as follows: first compute g a primitive root modulo p using Algorithm
1.4.4, then compute g_1 = g^{p-l} mod p^2. If g_1 != 1, g is a primitive root
modulo p^a for every a, otherwise g + p is.
Finally, note that when p is an odd prime, if g is a primitive root modulo
p^a then g or g + p^a (whichever is odd) is a primitive root modulo 2p^a.


Best regards,  jj

P.S.: the book is a "must have", with
"must" in big flaming letters.


* L. Edson Jeffery <lejeffery2 at gmail.com> [Dec 09. 2015 13:46]:
> Emmanuel,
> 
> With all respect, it seems that you are saying that the conjecture is true
> because it is true. We know (Gauss) that 2 is a primitive root modulo 3^k,
> for every k >= 1, and, for n>0, that 2^n modulo 3^k and 3^k are relatively
> prime, and that the sequence {2, 2^2, 2^3, ...} taken modulo 3^k is
> periodic, and that the period is 2*3^(k-1). Having stated those facts, how
> do we conclude that the periodicity of column k and the relative frequency
> of the digits 0,1,2 both follow as a consequence?
> 
> Ed Jeffery
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/