Maths Olympiad Prep

Library / /31 of 38

Number theory Difficulty 7.3 National olympiad, round 2 Prove it China

For any integer nn with n>1n > 1, let n=p1a1ptatn = p_1^{a_1} \cdots p_t^{a_t} be its standard factorization, write
ω(n)=t,Ω(n)=α1++αt. \omega(n) = t, \quad \Omega(n) = \alpha_1 + \cdots + \alpha_t.
Prove or disprove the following statement: Given any positive integer kk and any positive real numbers α\alpha and β\beta, there exists a positive integer nn with n>1n > 1 such that
ω(n+k)ω(n)>αandΩ(n+k)Ω(n)<β. \frac{\omega(n + k)}{\omega(n)} > \alpha \quad \text{and} \quad \frac{\Omega(n + k)}{\Omega(n)} < \beta.

Solution

The answer is YES.
From the definition of ω\omega and Ω\Omega, we have
ω(ab)ω(a)+ω(b),1 \omega(ab) \le \omega(a) + \omega(b), \qquad \textcircled{1}
Ω(ab)=Ω(a)+Ω(b),2 \Omega(ab) = \Omega(a) + \Omega(b), \qquad \textcircled{2}
for any positive integers a,ba, b. Given a fixed positive integer kk and positive real numbers α,β\alpha, \beta, we take a positive integer m>(ω(k)+1)αm > (\omega(k) + 1)\alpha. As there are infinitely many prime numbers, we can take a sufficiently large prime pp such that Ω(k)+1pm+logp2<β\frac{\Omega(k)+1}{p^m} + \log_p 2 < \beta, and take mm pairwise distinct prime numbers q1,q2,,qmq_1, q_2, \dots, q_m that are all greater than pp. We will show that n=2q1q2qmkn = 2^{q_1 q_2 \cdots q_m} k has the desired property.

First, we prove ω(n+k)ω(n)>α\frac{\omega(n+k)}{\omega(n)} > \alpha. Let n1=n+kk=2q1q2qm+1n_1 = \frac{n+k}{k} = 2^{q_1 q_2 \cdots q_m} + 1. As q1,q2,,qmq_1, q_2, \dots, q_m are all odd prime numbers, 2qi+1n12^{q_i} + 1 \mid n_1 when 1im1 \le i \le m, then di=2qi+13d_i = \frac{2^{q_i} + 1}{3} is an integer greater than 1.

Note that
(2r1,2s1)=2(r,s)1(2^r - 1, 2^s - 1) = 2^{(r,s)} - 1 for all positive integers r,sr, s, ③
and (qi,qj)=1 (ij)(q_i, q_j) = 1\ (i \neq j), we have
(di,dj)=13(2qi+1,2qj+1)13(22qi1,22qj1)=2(2qi,2qj)13=2213=1. \begin{aligned} (d_i, d_j) &= \frac{1}{3}(2^{q_i} + 1, 2^{q_j} + 1) \le \frac{1}{3}(2^{2q_i} - 1, 2^{2q_j} - 1) \\ &= \frac{2^{(2q_i, 2q_j)} - 1}{3} = \frac{2^2 - 1}{3} = 1. \end{aligned}
d1,d2,,dmd_1, d_2, \dots, d_m are the pairwise coprime factors of n1n_1, and each of them is greater than 1. Hence, ω(n1)m\omega(n_1) \ge m. From ① and the choice of mm, we have
ω(n+k)ω(n)ω(n1)ω(n)ω(n1)ω(k)+1mω(k)+1>α. \frac{\omega(n+k)}{\omega(n)} \ge \frac{\omega(n_1)}{\omega(n)} \ge \frac{\omega(n_1)}{\omega(k)+1} \ge \frac{m}{\omega(k)+1} > \alpha.

Next, we prove Ω(n+k)Ω(n)<β\frac{\Omega(n+k)}{\Omega(n)} < \beta. As q1q2qmq_1 q_2 \cdots q_m is an odd number and cannot be divided by 3, we have n1=2q1q2qm+1±3(mod9)n_1 = 2^{q_1 q_2 \cdots q_m} + 1 \equiv \pm 3 \pmod{9}, that is, 3n13 \nmid n_1. Suppose qq is a prime factor of n13\frac{n_1}{3} and qpq \le p, then
22q1q2qm1=(2q1q2qm1)n10(modq). 2^{2q_1 q_2 \cdots q_m} - 1 = (2^{q_1 q_2 \cdots q_m} - 1) \cdot n_1 \equiv 0 \pmod{q}.
From the Fermat's Little Theorem, 2q11(modq)2^{q-1} \equiv 1 \pmod{q}. From ③, q2(2q1q2qm,q1)1q \mid 2^{(2q_1 q_2 \cdots q_m, q-1)} - 1. From (q1,2q1q2qm)=(q1,2)2,q1<p<qi (i=1,2,,m)(q-1, 2q_1 q_2 \cdots q_m) = (q-1, 2) \le 2, q-1 < p < q_i\ (i = 1, 2, \dots, m), hence q221,q=3q \mid 2^2 - 1, q = 3. This contradicts that n13\frac{n_1}{3} is not a multiple of 3. Therefore, each prime factor of n13\frac{n_1}{3} is larger than pp. So n13>pΩ(n1/3)\frac{n_1}{3} > p^{\Omega(n_1/3)}. From ② and the choice of primes pp and q1,q2,,qmq_1, q_2, \dots, q_m, we have
Ω(n+k)=Ω(k)+Ω(3)+Ω(n13)<Ω(k)+1+logp(n13)<Ω(k)+1+logp(n11)=Ω(k)+1+q1q2qmlogp2, \begin{align*} \Omega(n+k) &= \Omega(k) + \Omega(3) + \Omega\left(\frac{n_1}{3}\right) < \Omega(k) + 1 + \log_p\left(\frac{n_1}{3}\right) \\ &< \Omega(k) + 1 + \log_p(n_1 - 1) \\ &= \Omega(k) + 1 + q_1 q_2 \cdots q_m \log_p 2, \end{align*}

\frac{\Omega(n+k)}{\Omega(n)} < \frac{\Omega(k) + 1 + q_1 q_2 \cdots q_m \log_p 2}{q_1 q_2 \cdots q_m} < \frac{\Omega(k) + 1}{p^m} + \log_p 2 < \beta. \quad \square

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 and solution reproduced as published; topic and difficulty added by this site.