A213514 - OEIS

%I #43 Apr 14 2019 09:45:21

%S 1,1,3,2,1,3,1,6,7,5,3,8,1,7,4,1,8,3,5,15,12,1,10,11,1,14,7,5,3,20,1,

%T 15,6,9,18,3,17,14,7,20,1,11,1,26,31,16,5,3,24,21,23,1,34,3,16,5,15,

%U 26,1,11,20,1,30,7,17,18,3,32,1,22,31,13,38,19,5,7,8,1,35,29,38,15,5,26,3,44,1,22,23,10

%N For composite n, remainder of n - 1 when divided by phi(n), where phi(n) is the totient function (A000010).

%C D. Lehmer conjectured that a(k) is never 0. He proved that if such k exists, the corresponding composite n must be odd, squarefree, and divisible by at least 7 primes. Cohen and Haggis showed that such n must be larger than 10^20 and have at least 14 prime factors.

%H Balarka Sen, <a href="/A213514/b213514.txt">Table of n, a(n) for n = 1..999</a>

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/TotientFunction.html">Totient Function</a> (MathWorld)

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Euler%27s_totient_function">Euler's totient function</a>

%e a(1) = 1 because the first composite number is 4 and 4 - 1 = 1 mod phi(4).

%e a(2) = 1 because the second composite is 6 and 6 - 1 = 1 mod phi(6).

%e a(3) = 3 because the third composite is 8 and 8 - 1 = 3 mod phi(8).

%t DeleteCases[Table[Mod[n - 1, EulerPhi[n]] - Boole[PrimeQ[n]], {n, 100}], -1] (* _Alonso del Arte_, Feb 15 2013 *)

%t Mod[#-1,EulerPhi[#]]&/@Select[Range[200],CompositeQ] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale_, Apr 14 2019 *)

%o (PARI) for(n=1,300,if(isprime(n)==0,print1((n-1)%eulerphi(n)",")))

%o (PARI) forcomposite(n=4,100,print1((n-1)%eulerphi(n)", ")) \\ _Charles R Greathouse IV_, Feb 19 2013

%Y Cf. A000010, A068494, A215486.

%K nonn,easy

%O 1,3

%A _Balarka Sen_, Feb 15 2013