Maths Olympiad Prep

Library / /5 of 24

Number theory Difficulty 4.9 AIME Prove it Croatia

Let aa and bb be positive integers such that 8a2+1=b28a^2 + 1 = b^2. Prove that abab is divisible by 33.

Solution

We have 8a2+1=b28a^2 + 1 = b^2, so b28a2=1b^2 - 8a^2 = 1.

Consider the equation modulo 33:

8a2+1b2(mod3)8a^2 + 1 \equiv b^2 \pmod{3}

Since 82(mod3)8 \equiv 2 \pmod{3}, we have:

2a2+1b2(mod3)2a^2 + 1 \equiv b^2 \pmod{3}

Now, a2a^2 modulo 33 can be 00 or 11:
- If a0(mod3)a \equiv 0 \pmod{3}, then a20a^2 \equiv 0.
- If a1(mod3)a \equiv 1 \pmod{3} or a2(mod3)a \equiv 2 \pmod{3}, then a21a^2 \equiv 1.

Case 1: a0(mod3)a \equiv 0 \pmod{3}

Then 2a2+10+1=1(mod3)2a^2 + 1 \equiv 0 + 1 = 1 \pmod{3}, so b21(mod3)b^2 \equiv 1 \pmod{3}.

Possible values for bb modulo 33 are 11 or 22 (since 1211^2 \equiv 1, 2212^2 \equiv 1).

Thus, ab0(mod3)ab \equiv 0 \pmod{3}.

Case 2: a1(mod3)a \equiv 1 \pmod{3} or a2(mod3)a \equiv 2 \pmod{3}

Then a21a^2 \equiv 1, so 2a2+121+1=30(mod3)2a^2 + 1 \equiv 2 \cdot 1 + 1 = 3 \equiv 0 \pmod{3}, so b20(mod3)b^2 \equiv 0 \pmod{3}.

Thus, b0(mod3)b \equiv 0 \pmod{3}, so ab0(mod3)ab \equiv 0 \pmod{3}.

In all cases, abab is divisible by 33.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.