Given a fixed positive integer $a\geq 9$. Prove: There exist finitely many positive integers $n$, satisfying: (1)$\tau (n)=a$ (2)$n|\phi (n)+\sigma (n)$ Note: For positive integer $n$, $\tau (n)$ is the number of positive divisors of $n$, $\phi (n)$ is the number of positive integers $\leq n$ and relatively prime with $n$, $\sigma (n)$ is the sum of positive divisors of $n$.
Problem
Source: 2014 China TST 2 Day 1 Q2
Tags: function, induction, number theory, relatively prime, number theory proposed
20.03.2014 16:33
Even if $a>2$, the proposition is true.
20.03.2014 16:46
for example $a$ is prime. What happened?
20.03.2014 17:12
There is a boring solution with using monotonicity of some function and induction on the number of prime factors of n. For writing an answer to the problem, all you need is patience.
25.04.2014 06:25
If $a$ is prime, $n=p^{a-1}$ for some $p$. Then we need $p^{a-1} | (p-1)p^{a-2} + \frac{p^{a+1}-1}{p-1} \iff p^{a-1} | (p-1)^2p^{a-2} + p^{a+1}-1 = p^{a-2}-1$ which is never true. So the problem is false, or it is written ambiguously. EDIT: Sorry, misread the problem. It asks for finitely many $n$.
26.04.2014 15:28
Its fintiely many $n$, so no solutions should be ok.
27.04.2014 20:44
Oh, I'm sorry, I read it incorrectly.
27.03.2015 03:12
Thank you yugrey: First note that if we write the canonical 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, fixing 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). $ Assume for the sake of contradiction there are infinitely many such sets and let $ S $ be the set of these sets - pick an element from $ S. $. It's well-known 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} $ so we have that $ \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). $ It's clear that there exists some $ N \in \mathbb{N} $ such that one of these primes is less than $ N, $ because otherwise we would have $ 1 < \frac{\phi(n) + \sigma(n)}{n} < 2. $ Now by infinite pigeonhole, there are an infinite number of sets in $ S $ that all share the same prime that is less than $ N. $ Looking at just these sets and repeating the argument over and over we have that every element of a set in $ S $ is bounded by some number so $ S $ is finite, contradiction . Therefore we are done.
27.03.2015 06:20
Yes this is my solution that I sent you over facebook chat. What a thief. But "repeating the argument over and over again" is not trivial. Here are the details, which I did not fully flesh out in the chat. So once you have infinite solutions with $p_1$ through $p_r$ fixed, say the product $(1-p_i^{-1})=A$ over $1 \le i \le r$. Say the product of $(1+p_i^{-1}+...p_i^{-a_i})=B$. Now, we have to deal with just $p_j$ as $r<j \le m$ runs, and we can assume there are solutions with all these $p_j>N$ for any fixed $N$ (arguing by contradiction, because else we could infinite pigeonhole to fix $p_{r+1}$, keep doing this until $r=m$, and finish). So $A(prod(1-p_j^{-1})+B(prod(1+...p_j^{-a_j})$ can be made absurdly close to $A+B$ by plugging in huge $p_j$. In the case posted above, $1<A+B<2$, so $A+B$ is clearly not an integer. Indeed we're rather obviously done if $A+B$ is not an integer. But if $A+B$ is an integer, then if we just jack up all the primes $(p_{r+1},...p_m)$ to $(p_{r+1}',...p_m')$ where $p_a'>p_b$ (where $a>r$, $b>r$) then I claim the value cannot stay the same. Why? Because $m>1$ (the case $m=1$ gives $n=p^r$, condition 2) implies $r=1$, and then $a=2$ so who cares), and so our function is increasing in $\frac {1} {p_j}$ for all $j$, since it's a polynomial in $p_j^{-1}$ with all the coefficients at least $0$, using the handy fact that something at least $1$ is greater than something less than $1$, so the linear term is positive and the rest are nonnegative. So then decreasing all of the $p_j^{-1}$ lowers the function, and we cannot have an infinite set of solutions that's always equal to $A+B$ exactly. So then our infinite set of solutions must have some $N$ such that there is a $p_j \le N$, and by infinite pigeonhole we have an infinite set with WLOG a fixed $p_{r+1}$. So keep going until we get an infinite set with $p_1$,.. $p_m$ all fixed, contradiction.
06.09.2020 20:52
10.07.2024 20:35
Isnt this problem next to trivial for china p2 everyone knows the idea of bounding ratios in single variable polynomial divisions thinking of generelazing it is pretty natural