cp's OEIS Frontend

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

%I A213514 #44 Feb 16 2025 08:33:17
%S A213514 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 A213514 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 A213514 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 A213514 For composite n, remainder of n - 1 when divided by phi(n), where phi(n) is the totient function (A000010).
%C A213514 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 A213514 Balarka Sen, <a href="/A213514/b213514.txt">Table of n, a(n) for n = 1..999</a>
%H A213514 Eric W. Weisstein, <a href="https://mathworld.wolfram.com/TotientFunction.html">Totient Function</a> (MathWorld)
%H A213514 Wikipedia, <a href="http://en.wikipedia.org/wiki/Euler%27s_totient_function">Euler's totient function</a>
%e A213514 a(1) = 1 because the first composite number is 4 and 4 - 1 = 1 mod phi(4).
%e A213514 a(2) = 1 because the second composite is 6 and 6 - 1 = 1 mod phi(6).
%e A213514 a(3) = 3 because the third composite is 8 and 8 - 1 = 3 mod phi(8).
%t A213514 DeleteCases[Table[Mod[n - 1, EulerPhi[n]] - Boole[PrimeQ[n]], {n, 100}], -1] (* _Alonso del Arte_, Feb 15 2013 *)
%t A213514 Mod[#-1,EulerPhi[#]]&/@Select[Range[200],CompositeQ] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale_, Apr 14 2019 *)
%o A213514 (PARI) for(n=1,300,if(isprime(n)==0,print1((n-1)%eulerphi(n)",")))
%o A213514 (PARI) forcomposite(n=4,100,print1((n-1)%eulerphi(n)", ")) \\ _Charles R Greathouse IV_, Feb 19 2013
%Y A213514 Cf. A000010, A068494, A215486.
%K A213514 nonn,easy
%O A213514 1,3
%A A213514 _Balarka Sen_, Feb 15 2013