Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|improve this question
    
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

2 Answers 2

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$.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.