# Find all positive integers $a$ for which there exists some positive integer $b$ s.t. $(2^a-1)\mid(b^2+9)$

Find all positive integers $a$ for which there exists some positive integer $b$ s.t.

$(2^a-1)\mid(b^2+9)$

-
Welcome to SE. It would be helpful if you explain what you tried so far and where you got stuck. This will help you get better answers to your question. – Ittay Weiss Nov 12 '12 at 6:46
This is an old question from an IMO Shortlist (1998?). – Evariste Sep 3 '13 at 8:31

Since this is homework, I'll limit myself to some hints.

First, handle the cases $a=1$ and $a=2$.

Then, for $a\gt2$, consider prime divisors congruent $3$ mod $4$ of $2^a-1$ and of $b^2+9$.

-

LEMMA. If $p=4k+3$ is a prime such that $p|a^2+b^2$ for any integer numbers $a,b$ then $p|a,p|b$.

Proof. If at least one of two numbers $a,b$ is divisible by $p$ then the other is also divisible by $p$.

If $p \nmid a,p \nmid b$ then by Fermat's Little Theorem we have $a^{p-1}=a^{4k+2} \equiv 1 \pmod{p}$ and $b^{p-1} =b^{4k+2} \equiv 1 \pmod{p}$. Hence $a^{4k+2}+b^{4k+2} \equiv 2 \pmod{p}$. But $p|a^2+b^2| a^{4k+2}+b^{4k+2}$ then $p=2$, a contradiction.

Thus, $p|a,p|b$.

SOLUTION. Let $a=2^k \cdot l$ with $k,l \in \mathbb{N}$ and $2 \nmid l$. It is to see that $a=1,2$ is a solution. If $a \ge 3$.

We have $2^a-1 \equiv 3 \pmod{4}$ then it is always exist a prime $p=4k+3$ is a divisor of $2^a-1$. Hence $p|b^2+9$. We get $p|3$ by the lemma. Thus, $p=3$.

If $l \ge 3$ then $2^l-1|2^a-1$. We also have $2^l-1 \equiv 3 \pmod{4}$. It follows that $2^l-1 \equiv 0 \pmod{3}$,a contradiction since $l$ is odd.

Thus, $l=1$. We get $a$ is a power of $2$.

-