A068494 a(n) = n mod phi(n).

0, 0, 1, 0, 1, 0, 1, 0, 3, 2, 1, 0, 1, 2, 7, 0, 1, 0, 1, 4, 9, 2, 1, 0, 5, 2, 9, 4, 1, 6, 1, 0, 13, 2, 11, 0, 1, 2, 15, 8, 1, 6, 1, 4, 21, 2, 1, 0, 7, 10, 19, 4, 1, 0, 15, 8, 21, 2, 1, 12, 1, 2, 27, 0, 17, 6, 1, 4, 25, 22, 1, 0, 1, 2, 35, 4, 17, 6, 1, 16, 27, 2, 1, 12, 21, 2, 31, 8, 1, 18, 19, 4

Offset: 1

Author

Benoit Cloitre, Mar 11 2002

Keywords

• easy
• nonn

Comments

By Lehmer's Conjecture, when n > 2 then a(n) = 1 if and only if n is prime. The Notices article states "Lehmer's Conjecture (1932). phi(n) | (n-1) if and only if n is prime." - Michael Somos, Oct 14 2011

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• D. H. Bailey and J. M. Borwein, Exploratory Experimentation and Computation, Notices of A. M. S. 58 (2011) 1410-1419, see p. 1416.

Crossrefs

Positions of particular numbers: 0: A007694, 1 (conjectured): A065091, 3: A350777\{1, 2, 3}.

Cf. A055516.

Programs

Haskell

a068494 n = mod n $ a000010 n  -- Reinhard Zumkeller, Oct 14 2011

Magma

[n mod EulerPhi(n): n in [1..100]]; // Vincenzo Librandi, Jul 19 2015

Mathematica

Table[Mod[n, EulerPhi[n]], {n, 100}] (* Alonso del Arte, Feb 15 2013 *)

PARI

for(n=1,150,print1(n%eulerphi(n),","))

PARI

{a(n) = n % eulerphi(n)}; /* Michael Somos, Oct 14 2011 */

Formula

b^(n - a(n)) == 1 (mod n) for every b coprime to n. - Thomas Ordowski, Jun 30 2017