Wednesday, November 30, 2011

Italian IMO Team Selection Test 1994 - Problem 2

Problem:
Find all prime numbers $p$ for which $\dfrac{2^{p-1}-1}{p}$ is a perfect square.

Solution:
Since $2^{p-1}-1$ is odd for all primes $p$, it's easy to see that $p \neq 2$. Moreover, by Fermat's Little Theorem we have $2^{p-1} \equiv 1 \pmod{p}$ for all primes $p \neq 2$, so $\dfrac{2^{p-1}-1}{p}$ is an integer and we want this integer to be a perfect square. Then, $$pn^2 = 2^{p-1} - 1, \quad n \in \mathbb{N}.$$ Since $p > 2$, $p-1$ is even and so we can write $$pn^2=(2^{\frac{p-1}{2}}-1)(2^{\frac{p-1}{2}}+1).$$ Both factor on the right hand side are odd and are relatively primes since their difference is $2$. This means that $p$ divides exactly one between the two factors and the other is a perfect square. If $p$ divides the first factor, we have $$2^{\frac{p-1}{2}}-1=pa^2, \qquad 2^{\frac{p-1}{2}}+1=b^2$$ where $a,b \in \mathbb{N}^*$. From the second equation we find $2^{\frac{p-1}{2}}=(b-1)(b+1)$ and these two factors are both powers of $2$ whose difference is $2$, so $b=3$ and $p=7$. If $p$ divides the second factor, we have $$2^{\frac{p-1}{2}}-1=a^2, \qquad 2^{\frac{p-1}{2}}+1=pb^2$$ and from the first equation,  if $p>3$ then $2^{\frac{p-1}{2}}-1=a^2 \equiv 3 \pmod{4}$, contradiction. So, it must be $p=3$ and for such value, $\dfrac{2^{3-1}-1}{3}=1$ which is a perfect square. In conclusion, the only prime numbers $p$ which satisfy the given condition are $p=3$ and $p=7$.

No comments:

Post a Comment