2
$\begingroup$

Let $n$ be some positive odd number. Prove, in terms of the pigeonhole principle, that there exists some positive integer $k$ such that $n\mid 2^k-1$.

$\endgroup$
  • 1
    $\begingroup$ Recall $\text{n } | \text{ } 2^{k - 1}$ is the same as $2^{k-1} \equiv 0 \mod \text{n}$. Is there any theorem you know for that is similar to this? $\endgroup$ – David Nov 7 '13 at 2:32
2
$\begingroup$

We use congruence notation. Consider the remainders when $2^1,2^2,2^3,\dots,2^n$ is divided by $n$. These remainders can take no values other than $1,2,3,\dots,n-1$.

The list $2^1,2^2,\dots, 2^n$ has $n$ numbers, and there are at most $n-1$ possible remainders. It follows that there exist integers $a$ and $b$, with $1\le a\lt b\le n$ such that $2^a\equiv 2^b\pmod{n}$. Thus $2^{b-a}\equiv 1\pmod{n}$.

$\endgroup$
  • $\begingroup$ IMHO, it should be mentioned that $0$ is not a possible remainder (because $n$ is odd) and that the last argument is a consequence of Gauss theorem. $\endgroup$ – Adren Jul 10 '18 at 16:46
  • $\begingroup$ Another version of the same result is as follows : if $n$ is an odd positive integer, then the binary representation of some multiple of $n$ contains only ones. $\endgroup$ – Adren Jul 10 '18 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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