1
$\begingroup$

Given a fixed positive integer $a\geq 9$. Prove there exist finitely many positive integers $n$, satisfying:

  1. $\tau (n)=a$
  2. $n|\varphi (n)+\sigma (n)$

My ideal is if i write the factorization $ n = \prod_{i = 1}^{m}p_i^{a_i}, $ then since $ \prod_{i = 1}^{m}(a_i + 1) = a, $ there are only a finite number of suitable $ (m, (a_1, a_2, \dots, a_m)) \in \mathbb{Z}^{+} \times \mathbb{N}^m. $ Therefore, we can fix a $ (m, (a_1, a_2, \dots, a_m)) \in \mathbb{Z}^{+} \times \mathbb{N}^m $. For the remainder of the proof, it suffices to show there are a finite number of sets of distinct primes $ (p_1, p_2, \dots, p_m) $ such that $ n = \prod_{i = 1}^{m}p_i^{a_i} $ and $ n \vert \phi(n) + \sigma(n)$. But how can I show there are finite $ (p_1, p_2, \dots, p_m) $?

$\endgroup$
2
$\begingroup$

Continue it like the following: Assume for the sake of contradiction there are infinitely many such sets and let $ T $ be the set of these sets. Pick an arbitrary set $S\in T$. It's clear that $ \phi(n) = \prod_{i = 1}^{m}(p_i^{a_i - 1}(p_i - 1)) $ and $ \sigma(n) = \prod_{i = 1}^{m}\frac{p_i^{a_i + 1} - 1}{p_i - 1} $ therefore $ \frac{\phi(n) + \sigma(n)}{n} = \prod_{i = 1}^{m}\frac{p_i - 1}{p_i} + \prod_{i = 1}^{m}\left(1 + \frac{1}{p_i} + \dots + \frac{1}{p_i^{a_i}}\right). $ Clearly these pimes have an upper bound (we'll call it $L$) because otherwise we would have $ 1 < \frac{\phi(n) + \sigma(n)}{n} < 2. $ Therefore it's clear that there are an infinite number of sets in $ T $ that all have the same prime $ p<L. $ Now going through the same procedure over and over for all sets, we have that every element of a set $ S\in T $ is bounded by some number so $ T $ is finite and our proof is complete.

P.S. If you're wondering about the part I said that if the prime factors don't have an upper bound, $\frac{\phi(n) + \sigma(n)}{n} < 2$ , here's the proof:
As we said, $ \frac{\phi(n) + \sigma(n)}{n} = \prod_{i = 1}^{m}\frac{p_i - 1}{p_i} + \prod_{i = 1}^{m}\left(1 + \frac{1}{p_i} + \dots + \frac{1}{p_i^{a_i}}\right). $ Now clearly $\prod_{i = 1}^{m}\frac{p_i - 1}{p_i}$ is always less than one so assume that $\prod_{i = 1}^{m}\frac{p_i - 1}{p_i}=1-s$. On ther other hand $\prod_{i = 1}^{m}\left(1 + \frac{1}{p_i} + \dots + \frac{1}{p_i^{a_i}}\right)$ can be arbitrarily close to one if $p$ doesn't have an upper bound so we'll choose one of the prime factors such that $\prod_{i = 1}^{m}\left(1 + \frac{1}{p_i} + \dots + \frac{1}{p_i^{a_i}}\right)<1+s$. Then we'll have $\frac{\phi(n) + \sigma(n)}{n} < 2$ and the proof is complete.

$\endgroup$
2
  • $\begingroup$ How can i prove that $\dfrac{\varphi(n)+\sigma(n)}{n}<2$ if $p_i$ goes to infinitely, i am stuck in here. $\endgroup$ – Zootopia Feb 3 at 10:35
  • $\begingroup$ I added details in the solution $\endgroup$ – Aryaaaaan Feb 3 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.