Maths Olympiad Prep

Library / /19 of 37

Number theory Difficulty 6.8 National olympiad Find the answer

Let n=p1a1p2a2ptatn=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t} be the prime factorisation of nn. Define ω(n)=t\omega(n)=t and Ω(n)=a1+a2++at\Omega(n)=a_1+a_2+\ldots+a_t. Prove or disprove:
For any fixed positive integer kk and positive reals α,β\alpha,\beta, there exists a positive integer n>1n>1 such that
i) ω(n+k)ω(n)>α\frac{\omega(n+k)}{\omega(n)}>\alpha
ii) Ω(n+k)Ω(n)<β\frac{\Omega(n+k)}{\Omega(n)}<\beta.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n=p1a1p2a2ptat n = p_1^{a_1} p_2^{a_2} \cdots p_t^{a_t} be the prime factorization of n n . Define ω(n)=t\omega(n) = t and Ω(n)=a1+a2++at\Omega(n) = a_1 + a_2 + \ldots + a_t. We aim to prove or disprove the following statements for any fixed positive integer k k and positive reals α\alpha and β\beta:

i) ω(n+k)ω(n)>α\frac{\omega(n+k)}{\omega(n)} > \alpha

ii) Ω(n+k)Ω(n)<β\frac{\Omega(n+k)}{\Omega(n)} < \beta.

To address statement (i), we need to show that lim supnω(n+k)ω(n)=\limsup_{n \to \infty} \frac{\omega(n+k)}{\omega(n)} = \infty. This can be demonstrated by considering the behavior of ω(p+k)\omega(p+k) for prime p p . Specifically, we show that lim suppω(p+k)=\limsup_{p \to \infty} \omega(p+k) = \infty.

We start by examining the sum pxω(p+k)\sum_{p \le x} \omega(p+k). For some y=xδ y = x^{\delta} with 0<δ<12 0 < \delta < \frac{1}{2} , let ωy(n)\omega_y(n) denote the number of prime factors of n n that are y\le y. It can be shown that ω(n)=ωy(n)+O(1)\omega(n) = \omega_y(n) + O(1). Thus,
pxω(p+k)=pxωy(p+k)+O(xlogx). \sum_{p \le x} \omega(p+k) = \sum_{p \le x} \omega_y(p+k) + O\left(\frac{x}{\log x}\right).

Using the Bombieri-Vinogradov Theorem, we obtain:
yπ(x;,k)=ylix1+O(xlogAx), \sum_{\ell \le y} \pi(x; \ell, -k) = \sum_{\ell \le y} \frac{\text{li} x}{\ell - 1} + O\left(\frac{x}{\log^A x}\right),
where π(x;,k)\pi(x; \ell, -k) counts primes px p \le x such that pk(mod) p \equiv -k \pmod{\ell} .

Summing over primes y\ell \le y, we get:
y11=loglogy+O(1). \sum_{\ell \le y} \frac{1}{\ell - 1} = \log \log y + O(1).

Therefore,
pxω(p+k)=π(x)loglogx+O(xlogx). \sum_{p \le x} \omega(p+k) = \pi(x) \log \log x + O\left(\frac{x}{\log x}\right).

Assuming ω(p+k)=O(1)\omega(p+k) = O(1) leads to a contradiction, implying lim suppω(p+k)=\limsup_{p \to \infty} \omega(p+k) = \infty. Hence, lim supnω(n+k)ω(n)=\limsup_{n \to \infty} \frac{\omega(n+k)}{\omega(n)} = \infty, proving statement (i).

For statement (ii), note that ω(n)Ω(n)\omega(n) \le \Omega(n). Therefore, Ω(n+k)Ω(n)<β\frac{\Omega(n+k)}{\Omega(n)} < \beta follows from ω(n+k)ω(n)>α\frac{\omega(n+k)}{\omega(n)} > \alpha by choosing appropriate α\alpha and β\beta.

Thus, both statements are proven to be true.

The answer is: \boxed{\text{True}}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.