(from Romania, 2000). Let $a$ be an odd integer, given by its binary representation. Find simply, from this representation, the smallest integer $n$ such that $a^{n}-1$ is divisible by $2^{2007}$.
. Euler's totient function of $2^{2007}$ is $2^{2006}$, so $n$ divides $2^{2006}$: it is a power of 2. Let $a=1+m \cdot 2^{k}$, where $m$ is an odd integer. We have

$$
a^{n}=1+n\left(m \cdot 2^{k}\right)+\frac{n(n-1)}{2}\left(m \cdot 2^{k}\right)^{2}+\cdots+\binom{n}{p}\left(m \cdot 2^{k}\right)^{p}+\cdots
$$

When $n=2^{q}$ is a power of 2, $\binom{n}{p}$ is at least divisible by $2^{q-\nu_{2}(p)}$, and the $p$-th term of the expansion of $a^{n}$ is divisible by $2^{q-\nu_{2}(p)+k p}$ which is strictly greater than $2^{q+k}$ if $p>1$ (assuming $k>1$). The highest power of 2 that divides $a^{n}-1$ is therefore limited by the second term of $a^{n}$. It is thus $2^{q+k}$. The number $n$ sought is therefore $2^{2007-k}$ where $k$ is the number of digits following the second-to-last 1 in the binary representation. For example, for 111000101, it is two.

If $k=1$, we actually have $a=-1+m \cdot 2^{k^{\prime}}$ with $k^{\prime}>1$. We then have a development with the same terms but with opposite signs, but the same reasoning applies, and $n=2^{2007-k^{\prime}}$, and $k^{\prime}$ is the number of 1s that follow the last zero in the binary representation of $a$, for example for 101011111, it is five.