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

(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

Crossrefs

Cf. A000010, A068494, A215486.

Sequence in context: A036585 A260454 A164848 * A130827 A070309 A287556

Adjacent sequences: A213511 A213512 A213513 * A213515 A213516 A213517

Keyword

nonn,easy

Author

Balarka Sen, Feb 15 2013

Status

approved