login
Numbers n such that every integer has a cube root mod n.
4

%I #41 May 12 2019 18:25:21

%S 1,2,3,5,6,10,11,15,17,22,23,29,30,33,34,41,46,47,51,53,55,58,59,66,

%T 69,71,82,83,85,87,89,94,101,102,106,107,110,113,115,118,123,131,137,

%U 138,141,142,145,149,159,165,166,167,170,173,174,177,178,179,187,191,197

%N Numbers n such that every integer has a cube root mod n.

%C A positive integer n is in the sequence if x^3 (modulo n) describes a bijection from the set [0...n-1] to itself.

%C Every member of the sequence is squarefree. If m and n are coprime members of the sequence, m*n is also a member.

%C All primes > 3 in this sequence are congruent to 5 mod 6. See A045309. - _Zak Seidov_, Feb 16 2013

%C Products of distinct members of A045309 (primes not 1 mod 3). - _Charles R Greathouse IV_, Apr 20 2015

%C This sequence gives all values, ordered increasingly, for which A257301 vanishes, i.e., A257301(a(n))=0 for any n. - _Stanislav Sykora_, May 26 2015

%H Robert Israel, <a href="/A074243/b074243.txt">Table of n, a(n) for n = 1..10000</a>(a(1) to a(1501) from _Zak Seidov_)

%H Dainis Zeps, <a href="https://doi.org/10.13140/RG.2.2.28885.27367">On Grinbergs' differential geometry and finite fields</a>, University of Latvia (2019).

%F a(n) ~ kn sqrt(log n) for some constant k. - _Charles R Greathouse IV_, Apr 20 2015

%e The number 30 is in the sequence because the function x^3 (mod 30) describes a bijection from [0...29] to itself. Thus every integer has a cube root, modulo 30.

%p N:= 1000: # to get all terms <= N

%p Primes:= {2,3} union select(isprime, {seq(6*i+5,i=0..floor((N-5)/6))}):

%p A:= {1}:

%p for p in Primes do

%p A:= A union map(`*`, select(`<=`, A, floor(N/p)),p)

%p od:

%p A;

%p # if using Maple 11 or earlier, uncomment the next line

%p # sort(convert(A,list)); # _Robert Israel_, Apr 20 2015

%t fQ[n_] := Sort[PowerMod[#, 3, n] & /@ Range@ n] == Range@ n - 1; Select[Range@ 200, fQ] (* _Michael De Vlieger_, Apr 20 2015 *)

%o (PARI) is(n)=my(f=factor(n)); if(n>1 && vecmax(f[,2])>1, return(0)); for(i=1,#f~, if(f[i,1]%3==1, return(0))); 1 \\ _Charles R Greathouse IV_, Apr 20 2015

%Y Cf. A045309, A257301.

%K easy,nonn

%O 1,2

%A _Jack Brennen_, Sep 19 2002

%E New name from _Charles R Greathouse IV_, Apr 20 2015