Example 9 (2006 National Training Team Problem) Prove: For any positive integers m,n, there always exists a positive integer k, such that 2k−m has at least n 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 m, assuming m is odd. We will prove that for any positive integer n, there exists kn such that 2kn−m has at least n distinct prime factors. (1) We will prove (1) using mathematical induction: (1) When n=1, 23m−m clearly has at least one prime factor; (2) Assume 2kn−m has at least n distinct prime factors, let An=2km−m, then (An,2)=1, and 2kn+φ(An2)−m≡2kn−m≡An(modAn2), so An∣2kn+φ(An2)−m, Take a prime pAn2kn+φ(An2)−m, by An2kn+ϵ(An2)−m≡1(modAn) we know p∤An. Therefore, 2p(An2)+kn−m has at least n+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.