India — Team Selection Test, 2010

We show that there is no such positive integer $n$. Suppose the contrary; assume that a positive integer $n$ exists such that $2^{2n+1} \equiv 2 \pmod n$ and $103 \nmid n$. Then $2^{2n+1} \equiv 2 \pmod{103}$ as well; and as such $2^{2n} \equiv 1 \pmod{103}$. Since $103$ is prime, Fermat's little theorem gives $2^{102} \equiv 1 \pmod{103}$. If $d_1 = \gcd(102, 2n)$, it follows that $2^{d_1} \equiv 1 \pmod{103}$. But $102 = 2 \times 3 \times 17$. It is easy to rule out $d_1 = 2, 3, 6$. Hence $17 \mid d_1$. In turn $17 \nmid n$.

Again, using that $17$ is a factor of $n$, we get $2^{2n+1} \equiv 2 \pmod{17}$ or $2^{2n} \equiv 1 \pmod{17}$. Now $17$ being a prime, Fermat's little theorem implies that $2^{16} \equiv 1 \pmod{17}$. If $d_2 = \gcd(16, 2n)$, we see that $d_2$ is a power of $2$ and $2^{d_2} \equiv 1 \pmod{17}$. We see that $d_2 = 2, 4$ do not fit in. Hence $d_2 = 8$ or $16$. But then $d_2 \nmid 2n$ shows that $4 \nmid n$. Hence $2^{2n+1} \equiv 2 \pmod 4$, which may be seen to be impossible. Hence no such $n$ exists.