A376032 - OEIS

%I #11 Sep 07 2024 16:40:16

%S 0,0,0,3,3,0,3,3,7,3,3,5,3,3,17,3,3,7,3,3,5,3,3,5,3,3,7,3,3,17,3,3,5,

%T 3,3,5,3,3,5,3,3,5,3,3,7,3,3,5,3,3,5,3,3,7,3,3,5,3,3,17,3,3,5,3,3,5,3,

%U 3,5,3,3,5,3,3,11,3,3,5,3,3,7,3,3,5,3,3

%N Least prime p that does not divide n such that 2^phi(n) == 1 (mod p), or 0 if no such prime exists.

%C There is such a prime for all n except for n = 1, 2, 3, and 6.

%H Amiram Eldar, <a href="/A376032/b376032.txt">Table of n, a(n) for n = 1..10000</a>

%H C. A. Nicol and J. L. Selfridge, <a href="https://www.jstor.org/stable/2324934">Problem E 3452</a>, Elementary Problems, The American Mathematical Monthly, Vol. 98, No. 7 (1991), p. 645; <a href="https://www.jstor.org/stable/2324978">Extraneous Primes</a>, Solution to Problem E 3452 by David Callan and Kenneth Rogers, ibid., Vol. 100, No. 4 (1993), p. 404; <a href="https://www.jstor.org/stable/2324230">Comment by Gerry Myerson</a>, ibid., Vol. 100, No. 10 (1993), p. 959.

%t a[n_] := Module[{phi = EulerPhi[n], p = 2}, While[Divisible[n, p] || PowerMod[2, phi, p] != 1, p = NextPrime[p]]; p]; a[1] = a[2] = a[3] = a[6] = 0; Array[a, 100]

%o (PARI) a(n) = {my(phi = eulerphi(n), p = 2); if(6 % n == 0, 0, while(!(n%p) || Mod(2, p)^phi != 1, p = nextprime(p+1)); p);}

%Y Cf. A000010 (phi).

%K nonn,easy

%O 1,4

%A _Amiram Eldar_, Sep 07 2024