Maths Olympiad Prep

Library / /18 of 92

Number theory Difficulty 5.9 AIME, harder Prove it Iran

We call an infinite set SNS \subseteq \mathbb{N} good if for all pairwise distinct integers aa, bb, cSc \in S, all positive divisors of acbcab\frac{a^c - b^c}{a - b} are in SS. For all positive integers n>1n > 1, prove that there exists a good set SS such that nSn \notin S.

Solution

Let L(z)L(z) be the smallest prime divisor of zz.

Lemma. If aa, bb, cNc \in \mathbb{N} such that aba \neq b we have
L(acbcab)L(abc) L\left(\frac{a^c - b^c}{a - b}\right) \geq L(abc)
Proof. Assume the contrary, then there should be an integer pp such that gcd(p,a)=gcd(p,b)=1\gcd(p, a) = \gcd(p, b) = 1 and pacbcabp \mid \frac{a^c-b^c}{a-b}. Now consider two cases, if ab(modp)a \equiv b \pmod{p} then by lifting the exponent lemma νp(acbc)=νp(ab)\nu_p(a^c-b^c) = \nu_p(a-b) which is a contradiction. If a≢b(modp)a \not\equiv b \pmod{p} then ordp(ab1)1ord_p(ab^{-1}) \neq 1 (b1b^{-1} is multiplicative inverse of bb modulo pp). But we know that ordp(ab1)cord_p(ab^{-1}) \mid c and we have p>ordp(ab1)>L(c)p > \text{ord}_p(ab^{-1}) > L(c) which is a contradiction.

Consider a set
Ak={xNL(x)k} A_k = \{x \in \mathbb{N} \mid L(x) \geq k\}
now if aa, bb, cAkc \in A_k and dacbcabd \mid \frac{a^c-b^c}{a-b} then by lemma we have L(d)<L(abc)<nL(d) < L(abc) < n and hence dAkd \in A_k. Now it is enough to take k>nk > n. ■

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.