For a positive integer $n$, denote by $\tau (n)$ the number of its positive divisors. For a positive integer $n$, if $\tau (m) < \tau (n)$ for all $m < n$, we call $n$ a good number. Prove that for any positive integer $k$, there are only finitely many good numbers not divisible by $k$.
Problem
Source: 2012 China TST - Quiz 1 - Day 2 - P5
Tags: number theory proposed, number theory
15.03.2012 11:52
this is a version of a problem from 2005 ISL.
16.03.2012 19:13
2005 ISL 25 is weaker than this one. The b-part is trivial concluded from this question. The a-part used this for $3^7.$ So we yet have to try. We name again the good number HD's. Assume we have a $k$ the question is wrong. Let $p$ be the biggest prime of it and $s$ be the exponent of $2.$ If we prove there are only finitely many HD's such that $v_p(n)<s+1$ we are done. Take a prime $q>p^{s+1}$ then it is obvious that if there is a HD $n$ such that $q|n$ then $v_p(n)>s.$ (just see the biggest prime of $n$ is taken only once, looking to the biggest three) So we now just have to prove it can't that " There are $\infty$ many HD's $n$ such that $q \not|n$ for some prime number $q$" Proof: If the statement is true, there will be a HD with an exponent $r>2q$ of the prime $2.$ But $2^{r-q)q}$ is smaller than $2^r$ and has more divisors, so we get the exponent can't be bigger than $r$ and so there are only finitely. **** It this correct? (I didn't understand the proofs of the original 05 question)
21.03.2012 10:25
We suppose $G$ is the set of all good numbers. Lemma 1:Suppose ${p_1} < {p_2} < {p_3} < ...$ are all primes, $\alpha ,r$ are positive integers, $a \in G$ satisfies $p_r^\alpha \left| a \right.$, then $n = {\left( {\prod\limits_{i = 1}^r {{p_i}} } \right)^\alpha }\left| a \right.$. Proof: If not, there exit a $1 \leqslant i < r$ which satisfies ${v_{{p_i}}}(a) = \beta < \alpha $, then $b = \frac{a}{{p_i^\beta p_r^\alpha }}p_i^\alpha p_r^\beta < a$, and $\tau (b) = \tau (a)$, contradiction. Lemma 2: For a prime number ${p_t}$, there exit a positive integer $M$, for any $a \in G$, if $a > M$,then ${p_t}\left| a \right.$. Proof: We take a positive integer $\alpha $ satisfies ${2^\alpha } > {p_t}$, $M = {\left( {{p_1}{p_2}...{p_{t - 1}}} \right)^{3\alpha }}$. For any $a \in G$, if $a > M$, and $(a,{p_t}) = 1$. By Lemma 1, all the prime divisors of $a$ are belong to $\left\{ {{p_1},{p_2},...,{p_{t - 1}}} \right\}$, so there exit a $1 \leqslant i \leqslant t - 1$, satisfies ${v_{{p_i}}}(a) = \beta > 3\alpha $. Because $p_i^\alpha \geqslant {2^\alpha } > {p_t}$, $b = \frac{a}{{p_i^\alpha }}{p_t} < a$.As $2(\beta - \alpha + 1) > (\beta + 1)$, we have $\tau (b) > \tau (a)$, contradiction. Lemma 3: For a prime number ${p_t}$, $\alpha $ is a positive integer, then there exit a positive integer $M$, for any $a \in G$, if $a > M$, then $p_t^\alpha \left| a \right.$. And so we have $n = {\left( {\prod\limits_{i = 1}^t {{p_i}} } \right)^\alpha }\left| a \right.$ by lemma 1. Proof: Take a prime ${p_r} > p_t^\alpha $, by lemma 2 there exit a positive integer $M$, for any $a \in G$, if $a > M$, then ${v_{{p_r}}}(a) = \gamma \geqslant 1$. IF ${v_{{p_t}}}(a) = \beta < \alpha $, then $b = \frac{a}{{{p_r}}}p_t^\alpha < a$. As $\frac{\gamma }{{\gamma + 1}}\frac{{\alpha + \beta + 1}}{{\beta + 1}} \geqslant \frac{{2\gamma }}{{\gamma + 1}} \geqslant 1$,we have $\tau (b) \geqslant \tau (a)$, contradiction. Proof of the problem: Suppose the biggest prime divisor of $k$ is ${p_t}$, take a positive integer $\alpha $ satisfies ${2^\alpha } > k$, the for any prime $p\left| k \right.$, ${v_p}(k) < \alpha $, hence $k\left| {n = {{\left( {\prod\limits_{i = 1}^t {{p_i}} } \right)}^\alpha }} \right.$. By lemma 3 there exit a positive integer $M$, for any $a \in G$, if $a > M$, then $n\left| a \right.$ ,and so $k\left| a \right.$.
06.04.2015 01:07
For the remainder of the proof, $ p_i $ will denote the $ i $th prime and the $ a_i $ will be nonnegative integers. Lemma 1: If $ n = \prod_{i = 1}^{\infty}p_i^{a_i} $ is good, then $ a_i \ge a_{i + 1} $ for all $ i \in \mathbb{N}. $ Proof: Assume for the sake of contradiction that $ n $ was good and $ a_{m + 1} > a_m $ for some $ m \in \mathbb{N}. $ Then it's clear that $ \tau\left(\frac{np_m^{a_{m + 1} - a_m}}{p_{m + 1}^{a_{m + 1} - a_k}}\right) = \tau(n) $ and $ \frac{np_m^{a_{m + 1} - a_m}}{p_{m + 1}^{a_{m + 1} - a_m}} < n, $ contradicting the fact that $ n $ is good. Lemma 2: For all $ m \in \mathbb{Z}^{+} $ there exists an $ N \in \mathbb{Z} $ such that for all good $ n > N $ we have that $ p_m \vert n. $ Proof: Let $ r = \left\lceil{\log_{2}{p_m}}\right\rceil. $ I claim that $ N = \left(\prod_{i = 1}^{m - 1}p_i\right)^{2r} $ suffices. Consider a good integer $ n > N $ and assume for the sake of contradiction $ p_m \nmid n. $ By Lemma 1 we have that $ p_m' \nmid n $ for all integers $ m' \ge m. $ Since $ n > N $ by the pigeonhole principle there exists a positive integer $ j < m $ such that $ a_j \ge 2r. $ But $ \tau\left(\frac{np_m}{p_j^r}\right) = \frac{2(a_j - r + 1)}{a_j + 1}\tau(n) > \tau(n) $ and since $ p_j^r \ge 2^r > p_m $ we have that $ \frac{np_m}{p_j^r} < n, $ contradicting the fact that $ n $ is good. Lemma 3: For all $ m, s \in \mathbb{Z}^{+} $ there exists an $ N \in \mathbb{Z} $ such that for all good $ n > N $ we have that $ p_m^s \vert n. $ Proof: We proceed with induction on $ s, $ where Lemma 2 proves the base case of $ s = 1. $ Assume for some $ t \in \mathbb{Z}^{+} $ that the lemma is true for all positive integers less than $ t. $ By Lemma 2 and the inductive hypothesis, there exists an integer $ N $ such that for all good $ n > N $ we have that $ p_m^{t - 1}p_r \vert n $ where $ p_r $ is a prime greater than $ p_m^t. $ Assume for the sake of contradiction that in one such $ n, $ we have that $ p_m^t \nmid n. $ Then we have that $ \tau\left(\frac{np_m^t}{p_r}\right) = 2\tau\left(\frac{n}{p_r}\right) \ge \tau(n) $ and since $ p_r > p_m^t $ we also have that $ \frac{np_m^t}{p_r} < n, $ contradicting the fact that $ n $ is good. The combination of Lemma 3 and Lemma 1 clearly prove the desired result.
15.09.2021 14:49
This is pretty much same as @above,yet a very different and interesting finish to the end.(I am not sure about the last part so please point out any mistake you find) Replace 'good' with 'dead' Claim: If $n=\prod_i p_i^{e_i}$ is an dead integer then:- (a) We have $e_1\ge e_2\ge e_3\ge\cdots$. (b) $n$ must be divisible by the first $k$ primes. Proof: Note that permuting the exponents in the prime factorization does not change the value of $d(n)$, so if the $e_i$'s were non increasing, we could permute them to be non increasing, decreasing the value of $n$ while maintaining the value of $d(n)$,which is alive a contradiction to the graveyard. For part(b),Let $n=\prod^m_{j=1} p_j^{\alpha_j}$ be dead. Then $d(a)=d(n)$ where $a=\prod^m_{j=1} q_j^{\alpha_j}$ and $a \le n$. So $a=n$ and the claim is true. $\blacksquare$ Let $p_i$ be the ith prime.Define a process Reviving:Given a dead number $\prod p_i^{a_i}$,we call another dead number totally revived with respect to $p_{M}$ if we shift exponents ${a_i} \rightarrow {a_i}+X$ and $p_i^{X}>p$ Claim: For all $ m, s \in \mathbb{Z}^{+} $ there exists an $ N \in \mathbb{Z} $ such that for all good $ n > N $ we have that $ p_m^s \vert n. $ Proof: We'll use induction where the base case is clear by the last claim.Suppose that for $s=n$ it works and we will show that $s=n+1$ also works. Suppose that the nth number is $M=\prod p_i^{a_i}$ and we totally revive it to get another dead number $T_r=\prod p_i^{A_i} $ Now observe that $\max(d(\frac{p_s}{p_1}M),...........,d(\frac{p_s}{p_1 p_2........p_i}M)) \ge d(T_r)$,contradiction so we are done.$\blacksquare$