4
$\begingroup$

For which values of $m$ do there exist infinitely many $n$ such that $m$ divides $\phi(n)$?

Now, I know $\phi(n)$ is even for $n >2$, so clearly $m$ can’t be an odd number (except $1$). So $m=2$ clearly satisfies this, so I was wondering do all even integers satisfy this? Or just even integers which are of the form $p-1$ for a prime $p$?

$\endgroup$
3
  • $\begingroup$ Odd numbers can divide even numbers ( as $3$ divides $6$, say). For instance, every prime $p$ divides $\varphi(p^a)$ for all $a>1$ so all primes are examples of what you want. $\endgroup$
    – lulu
    May 22, 2018 at 15:38
  • 2
    $\begingroup$ I would conjecture that there exists no $m$, such that $m$ divides only a finite number of $\phi(n)$. $\endgroup$
    – user
    May 22, 2018 at 15:40
  • $\begingroup$ Notice if $\phi (p^k) = (p-1)p^{k-1}$ (for prime $p$) so if $m = p^k$ then $m|phi(p^{k+a})$ for all positive $a$. And so all $p^k$ will divide an infinite number. And as $\phi$ is multiplicative over relatively prime numbers then all $m = \prod p_i^{k_i}$ will divide an infinite $\phi(\prod p_i^{k_i + a_i}$. So any number that can be written as $ m= \prod p_i^{k_i}$ for $p_i$ prime. How many numbers can be written as a product of powers of primes? $\endgroup$
    – fleablood
    May 22, 2018 at 16:11

2 Answers 2

Reset to default
4
$\begingroup$

Every $m$ works.

Pf: if $m=\prod p_i^{a_i}$ then $m$ divides $\varphi(n)$ for any $n$ of the form $n=\prod p_i^{b_i}$ with $b_i>a_i$ for all $i$.

$\endgroup$
1
$\begingroup$

" I know ϕ(n) is even for n>2, so clearly m can’t be an odd number (except 1)"

Odd numbers can't be divided BY even numbers (not even 1), but odd numbers can divide even numbers. If $m$ is odd then $m\mid 2m$, of course.

I'm afraid once you realize this question is what numbers can divide Totient values, and not the other way-- what Totient numbers can divide other numbers-- this question becomes trivial:

All numbers.

If $m = \prod p_i^{k_i}$ is the prime factorization of $m$.

And $n = \prod q_i^{m_i}$ is the prime factorization of $n$ then $\phi(n) =\prod (q_i - 1) \prod q_i^{m_i - 1}$.

Obviously we can set the $q_i = p_i$ and then $m_i > k_i$ and $m|\phi(n)$. And that's not the only way. Clearly it is always possible that some $p_j^{k_j}|\prod (q_i -1)$ as well.

As an example:

Let $m = \prod p_i^{k_i}$. Let $n = \prod p_i^{k_i+a_i}$.

Then $\phi(n) = \prod (p_i-1)\prod p_i^{k_i + a_i-1} = m*\prod (p_i - 1)\prod p_i^{a_i - 1}$.

......

$\endgroup$

You must log in to answer this question.

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