Maths Olympiad Prep

Library / /11 of 46

Number theory Difficulty 5.6 AIME, harder Prove it Russia

Given integers x,y[2,100]x, y \in [2, 100], prove that there exists a positive integer nn such that the number x2n+y2nx^{2^n} + y^{2^n} is composite.

(S. Berlov, A. Kanel-Belov)

Solution

If x=yx = y, then n=1n = 1 works, since x2+y2x^2 + y^2 is an even number greater than 22.

Now assume xyx \neq y. In this case, we will show that for some nn, the number x2n+y2nx^{2^n} + y^{2^n} is divisible by 257257 and not equal to 257257. Then it will be composite, as required.

Suppose x2n+y2n=257x^{2^n} + y^{2^n} = 257. Let a=x2n1a = x^{2^{n-1}}, b=y2n1b = y^{2^{n-1}}. Then a2+b2=257a^2 + b^2 = 257, and if aba \ge b, then a=16a = 16, b=1b = 1 (the cases a=12,13,14,15a = 12, 13, 14, 15 are easily checked; if a11a \le 11, then b2a2<257/2b^2 \le a^2 < 257/2, which is impossible). But this contradicts the condition x,y>1x, y > 1. Thus, x2n+y2n257x^{2^n} + y^{2^n} \neq 257.

It remains to check only that for some nn, the number x2n+y2nx^{2^n} + y^{2^n} is divisible by 257257.

Since yy is not divisible by the prime number 257257, there exists a natural qq such that xqy(mod257)x \equiv qy \pmod{257}. Since xyx \neq y and 0<x+y<2570 < x + y < 257, we get q±1(mod257)q \neq \pm 1 \pmod{257}. Also, q0(mod257)q \neq 0 \pmod{257}, since xx is not divisible by 257257.

Since 257257 is prime, by Fermat's little theorem, the number q2561=(q1)(q+1)(q2+1)(q22+1)(q27+1)q^{256} - 1 = (q-1)(q+1)(q^2+1)(q^{2^2}+1) \dots (q^{2^7} + 1) is divisible by 257257. The first two factors are not divisible by 257257, so for some n{1,2,,7}n \in \{1, 2, \dots, 7\}, the number q2n+1q^{2^n} + 1 is divisible by 257257. But then the number x2n+y2ny2n(q2n+1)(mod257)x^{2^n} + y^{2^n} \equiv y^{2^n} (q^{2^n} + 1) \pmod{257} is also divisible by 257257.

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.