A213514 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

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.

LINKS

Balarka Sen, Table of n, a(n) for n = 1..999

Eric W. Weisstein, Totient Function (MathWorld)

Wikipedia, Euler's totient function

EXAMPLE

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).

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 *)

PROG