Mathematics desk
< February 1	<< Jan \| February \| Mar >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 2

Iterated totients and primitive roots

Do there exist arbitrarily long sequences $(n,\phi (n),\phi (\phi (n)),...,\phi ^{k}(n))$ where there are primitive roots modulo all members of the sequence except the last (or equivalently, the automorphism group of the cyclic group $\mathbb {Z} /(\phi ^{j}(n))$ is isomorphic to the cyclic group $\mathbb {Z} /(\phi ^{j+1}(n))$ for $0\leq j<k$ )? If not, then what is the upper bound on the lengths of such sequences? GeoffreyT2000 (talk) 22:55, 2 February 2019 (UTC)[reply]

Take n = 2⋅3^k. This starts a sequence of length k+1 since φ(2⋅3^k) = 2⋅3^k-1 and each of the multiplicative groups mod 2⋅3^k is cyclic. (According to Multiplicative group of integers modulo n#Structure, the multiplicative group mod n is cyclic iff n is 1, 2, 4, p^k or 2p^k.) Another possibility is n=2p, where p is the last entry in a Cunningham chain, but it isn't known if there are such chains of arbitrarily long length. The article lists some long examples through and more examples can be found by following the OEIS links in the article. Pretty sure @PrimeHunter: will have more expertise on this. --RDBury (talk) 15:04, 3 February 2019 (UTC)[reply]

Sorry, I'm not contributing further to this. PrimeHunter (talk) 03:12, 4 February 2019 (UTC)[reply]