Maths Olympiad Prep

Library / /220 of 299

Number theory Difficulty 7.0 National Olympiad Prove it Iran

If d(n)d(n) is the number of positive divisors of nn, prove that there exists a natural number nn such that:
iN, i1402:d(n)d(n±i)>1401. \forall i \in \mathbb{N},\ i \le 1402 : \frac{d(n)}{d(n \pm i)} > 1401.

Solution

Let n=p1α1psαsn = p_1^{\alpha_1} \cdots p_s^{\alpha_s}. We define Ω(n)=α1++αs\Omega(n) = \alpha_1 + \cdots + \alpha_s.
Lemma 1. d(n)2Ω(n)d(n) \le 2^{\Omega(n)}
Proof.
1is:2αiαi+1    2Ω(n)d(n) \forall 1 \le i \le s : 2^{\alpha_i} \ge \alpha_i + 1 \implies 2^{\Omega(n)} \ge d(n)

We denote prime numbers less than 14021402 as q1,,qlq_1, \dots, q_l and the rest of the prime numbers as p1<p2<p_1 < p_2 < \dots. We choose n=q1αqlαp1pkn = q_1^\alpha \cdots q_l^\alpha p_1 \cdots p_k where α,k\alpha, k will be determined later.
Suppose α\alpha is large enough such that
1tl, i1402:vqt(i)<α \forall 1 \le t \le l,\ i \le 1402 : v_{q_t}(i) < \alpha
To do so we restrict α>log21402\alpha > \log_2 1402. Now if for a prime number like qq and a number less than 14021402 like ii we have qiq \mid i then q{q1,,ql}q \in \{q_1, \dots, q_l\} so qniq \mid \frac{n}{i}. Thus gcd(i,ni±1)=1\gcd(i, \frac{n}{i} \pm 1) = 1.
d(n±i)=d(i)d(ni±1)14022Ω(ni±1)14022logpk+1(ni±1)14022logpk+1(n+1) d(n \pm i) = d(i)d\left(\frac{n}{i} \pm 1\right) \le 1402 \cdot 2^{\Omega\left(\frac{n}{i} \pm 1\right)} \le 1402 \cdot 2^{\log_{p_{k+1}}\left(\frac{n}{i} \pm 1\right)} \le 1402 \cdot 2^{\log_{p_{k+1}}(n+1)}
It is enough to show that
(α+1)l×2k>1401×1402×2logpk+1(n+1) (\alpha + 1)^l \times 2^k > 1401 \times 1402 \times 2^{\log_{p_{k+1}}(n+1)}
By adding the condition to the choice of α\alpha that (α+1)l>1401×1402(\alpha + 1)^l > 1401 \times 1402 it remains to prove klogpk+1(n+1)k \ge \log_{p_{k+1}}(n+1).
    pk+1k>q1αqlαp1pk \iff p_{k+1}^k > q_1^\alpha \cdots q_l^\alpha p_1 \cdots p_k
We may choose kk such that pk>q1αqlαp_k > q_1^\alpha \cdots q_l^\alpha. This ends the proof.

We shall indeed prove that for all k,mk, m there is a positive integer n>1n > 1 such that d(n)d(n±i)>m\frac{d(n)}{d(n \pm i)} > m, i=1,,ki = 1, \dots, k. Let C=max{d(1),,d(k)}C = \max\{d(1), \dots, d(k)\} and let ss be a positive integer such that 2s1>Cm2^{s-1} > Cm. Let pip_i be the ii-th prime number, chose a positive integer ll such that ps+l>k!p1psp_{s+l} > k!p_1 \dots p_s. Taking n=k!p1ps+ln = k!p_1 \dots p_{s+l} then n±in \pm i for all i=1,,ki = 1, \dots, k is greater than ii and is also divisible by ii. Then, for all i=1,,ki = 1, \dots, k;
n±i=iq1α1qrαr, n \pm i = i q_1^{\alpha_1} \dots q_r^{\alpha_r},
Where q1<<qrq_1 < \dots < q_r be prime numbers. Thus,
n±i=i(k!ip1ps+l±1). n \pm i = i \left( \frac{k!}{i} p_1 \dots p_{s+l} \pm 1 \right).
That is, n±ii\frac{n \pm i}{i} are divisible by primes greater than p1,,ps+lp_1, \dots, p_{s+l}. Therefore, q1>ps+l>k!p1psq_1 > p_{s+l} > k!p_1 \dots p_s that is, q1>1+k!p1psq_1 > 1 + k!p_1 \dots p_s hence, pk+1pl+s<q1sp_{k+1} \dots p_{l+s} < q_1^s. Thus,
q1s+1>k!p1ps+q1s=n+q1s>n+q1n+k. q_1^{s+1} > k! p_1 \dots p_s + q_1^s = n + q_1^s > n + q_1 \ge n + k.
Yielding q1l+1>n±iq_1^{l+1} > n \pm i. That is, q1l+1>q1α1qrαrq1α1++αrq_1^{l+1} > q_1^{\alpha_1} \dots q_r^{\alpha_r} \ge q_1^{\alpha_1+\dots+\alpha_r}.

Then, l+1>α1++αrrl+1 > \alpha_1 + \dots + \alpha_r \ge r to find l+1+r>(1+α1)++(1+αr)l+1+r > (1+\alpha_1)+\dots+(1+\alpha_r).
Hence,
d(n±i)=d(i)(1+α1)++(1+αr)C((1+α1)++(1+αr)r)r<C(l+1+rr)r d(n \pm i) = d(i)(1 + \alpha_1) + \dots + (1 + \alpha_r) \le C \left( \frac{(1 + \alpha_1) + \dots + (1 + \alpha_r)}{r} \right)^r < C \left( \frac{l+1+r}{r} \right)^r
Finally, (1+l+1r)r<(1+l+1l+1)l+1=2l+1(1 + \frac{l+1}{r})^r < (1 + \frac{l+1}{l+1})^{l+1} = 2^{l+1}. Yielding d(n±i)<C2l+1d(n \pm i) < C \cdot 2^{l+1}. Since d(n)>2s+1d(n) > 2^{s+1} we find that
d(n)d(n±i)>2s1C>m. \frac{d(n)}{d(n \pm i)} > \frac{2^{s-1}}{C} > m.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.