3
$\begingroup$

Are there infinitely many integers that do not divide any totient number?

My try:

If $a|b$ then $\phi(a)|\phi(b)$, so the main question would be equivalent to asking wether there are infinitely many integers that do not divide $\phi(p)$. We also know that $\phi(p)=p-1$. Then,

Are there infinitely many integers that do not divide any number of the form $p-1$? Would Dirichlet's Theorem on Arithmetic Progressions be enough to disprove it?

Thank you.

$\endgroup$
4
  • $\begingroup$ Do you know of any integer that does not divide any totient number? I've searched the odd integers less than 100 and not found a single one. $\endgroup$
    – Lisa
    Commented Feb 2, 2017 at 22:22
  • 1
    $\begingroup$ Dirichlet's Theorem ensures that for all $n$ there is a prime of the form $p=kn+1$. Hence, $n$ divides $p-1$. $\endgroup$
    – Crostul
    Commented Feb 2, 2017 at 22:24
  • 1
    $\begingroup$ @Lisa No, I have not tried to compute results. Maybe every number is a divisor of a totient number $\endgroup$
    – user3141592
    Commented Feb 2, 2017 at 22:27
  • $\begingroup$ Of interest here: oeis.org/A066678 $\endgroup$
    – Lisa
    Commented Feb 2, 2017 at 22:44

1 Answer 1

Reset to default
2
$\begingroup$

Marking this community wiki as I'm just fleshing out the comments:

No, there aren't infinitely many integers that do not divide any totient number, in fact, there are none. Unless maybe you want to count 0 as such a number.

But yes, Dirichlet's theorem on arithmetic progressions is enough to disprove the existence of totient nondivisors, since, as you note, $\phi(p) = p - 1$ for $p$ prime.

Consider the number 8 for example. Obviously 9 is not prime. But Dirichlet tells us there are infinitely many primes of the form $8k + 1$. So if $8k + 1$ is prime, then $\phi(8k + 1) = 8k$, confirming that 8 divides infinitely many totients of primes.

Of course that's not the only way a number can be a totient. 8 is itself the totient of 15, 16, 20, 24, 30, none of which are primes.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .