Competition problem — Number theory

Library / /2 of 155

Number theory Difficulty 4.4 AIME Prove it Saudi Arabia

Let $k$ be a positive integer. Prove that there exist integers $x, y$ , neither of which divisible by $7$ such that $x^{2} + 6 y^{2} = 7^{k}$ .

Solution

Take $x_{1} = y_{1} = -1$ , and the following relations
$x_{k+1} = x_{k} - 6 y_{k}, \quad y_{k+1} = x_{k} + y_{k}.$
for $k = 1, 2, 3, \ldots$

One can check that
$x_{k+1}^{2} + 6 y_{k+1}^{2} = 7 \left( x_{k}^{2} + 6 y_{k}^{2} \right)$
and
$x_{k} \equiv y_{k} \equiv (-1)^{k} \pmod{7}.$
Hence, there exist the integer $x = x_{k}, y = y_{k}$ satisfy the given condition.

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.