Maths Olympiad Prep

Library / /63 of 120

Number theory Difficulty 5.4 AIME, harder Prove it Saudi Arabia

Consider the set S={(a+b)7a7b7:a,bZ}S=\{(a+b)^{7}-a^{7}-b^{7}: a, b \in \mathbb{Z}\}. Find the greatest common divisor of all members in SS.

Solution

Let dd be the greatest common divisor of the numbers in SS. Since 272=126=2327S2^{7}-2=126=2 \cdot 3^{2} \cdot 7 \in S for x=y=1x=y=1, one gets that dd divides 126126. Now, for x=2x=2 and y=1y=1, one gets (2+1)7271=37271S(2+1)^{7}-2^{7}-1=3^{7}-2^{7}-1 \in S, therefore dd will divide the number (37271)+(272)=373(3^{7}-2^{7}-1)+(2^{7}-2)=3^{7}-3. Since 99 does not divide 3733^{7}-3, it follows that dd divides 126/3=42126 / 3=42.

Let us check that d=42d=42, i.e. the prime numbers 22, 33 and 77 divide (x+y)7x7y7(x+y)^{7}-x^{7}-y^{7}, for all integers xx and yy. Notice it is enough to show that 4242 divides a7aa^{7}-a for all integers aa, since one can write
(x+y)7x7y7=((x+y)7(x+y))(x7x)(y7y).(x+y)^{7}-x^{7}-y^{7}=\left((x+y)^{7}-(x+y)\right)-\left(x^{7}-x\right)-\left(y^{7}-y\right).
But a7a=a(a1)(a+1)(a2a+1)(a2+a+1)a^{7}-a=a(a-1)(a+1)\left(a^{2}-a+1\right)\left(a^{2}+a+1\right). Now, 22 divides a(a1)a(a-1), 33 divides a(a1)(a+1)a(a-1)(a+1), while 77 divides a7aa^{7}-a, by Fermat's Little Theorem.

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.