Вот наиболее короткое доказательство.
Рассмотрим числа $2^0-1$, $2^1-1$, $\ldots$, $2^n-1$. Этих чисел $a+1$. Какие-то два из них дают одинаковые остатки при делении на $a$, потому что различных таких остатков существует всего $a$ (это рассуждение называется «принцип Дирихле», о его применениях рассказывалось в статье А. Орлова в «Кванте» №7). Пусть, скажем, числа $2^k-1$ и $2^m-1$ дают одинаковые остатки при делении на $a$ и $k\lt m$. Тогда число $(2^m-1)-(2^k-1)=2^k(2^{m-k}-1)$ делится на $a$ и, поскольку $a$ нечётно, $2^{m-k}-1$ делится на $a$.
Точно так же доказывается и более общий факт: если натуральные числа $a$ и $c$ взаимно просты, то найдётся такое натуральное $b$, что $c^b-1$ делится на $a$. Многие читатели заметили, что утверждение задачи вытекает из следующей теоремы Эйлера: для любых натуральных $a$ и $c$ число $c^{\varphi(a)+1}-c$ делится на $a$, где $\varphi(a)$ — количество натуральных чисел, меньших $a$ и взаимно простых с ним, и даже приводят формулу для вычисления «функции Эйлера»
$$
\varphi(p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_r^{\alpha_r})=
(p_1^{\alpha_1}-p_1^{\alpha_1-1})(p_2^{\alpha_2}-p_2^{\alpha_2-1})\ldots
(p_r^{\alpha_r}-p_r^{\alpha_r-1}).
$$
