A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.

1, 3, 7, 5, 11, 7, 29, 15, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 25, 43, 23, 47, 35, 101, 53, 81, 29, 59, 31, 311, 51, 67, 103, 71, 37, 149, 191, 79, 41, 83, 43, 173, 69, 181, 47, 283, 65, 197, 101, 103, 53, 107, 81, 121, 87, 229, 59, 709, 61, 367, 311, 127, 85

Offset: 1

Author

Melvin J. Knight (knightmj(AT)juno.com), May 25 2001

Keywords

• nonn

Comments

Conjecture: a(n) is odd for all n. Verified up to n <= 3*10^5. - Jianing Song, Feb 21 2021

The conjecture above is false because a(16842752) = 33817088; see A002181 and A143510. - Flávio V. Fernandes, Oct 08 2023

Examples

			a(48) = 65 because phi(65) = phi(5)*phi(13) = 4*12 = 48 and no smaller integer m has phi(m) divisible by 48.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
• Ho-joo Lee and Gerald Myerson, Consecutive Integers Whose Totients Are Multiples of n: 10837, The American Mathematical Monthly, Vol. 110, No. 2 (Feb., 2003), pp. 158-159.
• Pieter Moree and Hans Roskam, On an arithmetical function related to Euler's totient and the discriminator, Fib. Quart., Vol. 33, No. 4 (1995), pp. 332-340.
• József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, pp. 1-8.

Crossrefs

Cf. A000010, A066674, A066675, A066676, A066678, A067005.

Cf. A233516, A233517 (records).

Cf. A005179 (analog for number of divisors), A070982 (analog for sum of divisors).

Programs

Mathematica

a = ConstantArray[1, 64]; k = 1; While[Length[vac = Rest[Flatten[Position[a, 1]]]] > 0, k++; a[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; a  (* Ivan Neretin, May 15 2015 *)

PARI

a(n) = my(s=1); while(eulerphi(s)%n, s++); s;
vector(100, n, a(n))

Python

from sympy import totient as phi
def a(n):
  k = 1
  while phi(k)%n != 0: k += 1
  return k
print([a(n) for n in range(1, 65)]) # Michael S. Branicky, Feb 21 2021

Formula

Sequence is unbounded; a(n) <= n^2 since phi(n^2) is always divisible by n.

If n+1 is prime then a(n) = n+1.

a(n) = min{ k : phi(k) == 0 (mod n) }.

a(n) = a(2n) for odd n > 1. - Jianing Song, Feb 21 2021