Olympiad Maths Prep

Track / Stage 7 / 133 of 300 #1533 of 2000

Problem 1533

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.2 Prove it

Example 9 (2006 National Training Team Problem) Prove: For any positive integers m,nm, n, there always exists a positive integer kk, such that 2km2^{k} - m has at least nn distinct prime factors.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

Prove that for a fixed mm, assuming mm is odd. We will prove that for any positive integer nn, there exists knk_{n} such that 2knm2^{k_{n}}-m has at least nn distinct prime factors.
(1)
We will prove (1) using mathematical induction:
(1) When n=1n=1, 23mm2^{3m}-m clearly has at least one prime factor;
(2) Assume 2knm2^{k_{n}}-m has at least nn distinct prime factors, let An=2kmmA_{n}=2^{k_{m}}-m, then (An,2)=1\left(A_{n}, 2\right)=1, and 2kn+φ(An2)m2knmAn(modAn2)2^{k_{n}+\varphi\left(A_{n}^{2}\right)}-m \equiv 2^{k_{n}}-m \equiv A_{n}\left(\bmod A_{n}^{2}\right), so An2kn+φ(An2)mA_{n} \mid 2^{k_{n}+\varphi\left(A_{n}^{2}\right)}-m,
Take a prime p2kn+φ(An2)mAnp \left\lvert\, \frac{2^{k_{n}+\varphi\left(A_{n}^{2}\right)}-m}{A_{n}}\right., by 2kn+ϵ(An2)mAn1(modAn)\frac{2^{k_{n}}+\epsilon\left(A_{n}^{2}\right)-m}{A_{n}} \equiv 1\left(\bmod A_{n}\right) we know pAnp \nmid A_{n}.
Therefore, 2p(An2)+knm2^{p\left(A_{n}^{2}\right)+k_{n}}-m has at least n+1n+1 distinct prime factors.
By mathematical induction, the conclusion holds.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.