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

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, 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, 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

Offset: 1

Author

Balarka Sen, Feb 15 2013

Keywords

• nonn
• easy

Comments

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.

Examples

			a(1) = 1 because the first composite number is 4 and 4 - 1 = 1 mod phi(4).
a(2) = 1 because the second composite is 6 and 6 - 1 = 1 mod phi(6).
a(3) = 3 because the third composite is 8 and 8 - 1 = 3 mod phi(8).
		

Links

• Balarka Sen, Table of n, a(n) for n = 1..999
• Eric W. Weisstein, Totient Function (MathWorld)
• Wikipedia, Euler's totient function

Crossrefs

Cf. A000010, A068494, A215486.

Programs

Mathematica

DeleteCases[Table[Mod[n - 1, EulerPhi[n]] - Boole[PrimeQ[n]], {n, 100}], -1] (* Alonso del Arte, Feb 15 2013 *)
Mod[#-1,EulerPhi[#]]&/@Select[Range[200],CompositeQ] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Apr 14 2019 *)

PARI

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

PARI

forcomposite(n=4,100,print1((n-1)%eulerphi(n)", ")) \\ Charles R Greathouse IV, Feb 19 2013