Theory of Congruences

Question

There is a problem in Elementary Number Theory by David Burton - We need to show that $0, 1, 2, 2^2, 2^3, \dots , 2^9$ form a complete set of residues modulo $11$. I tried this way - we need to show that $11 \nmid 2^r(2^{r-s} - 1)$ where $r > s$ and $r, s = 0, 1, 2, \dots , 9$. It is obvious that $11 \nmid 2^r$ but how to show that $11 \nmid 2^{r-s} - 1$ without actual verifying each value of $2^{r-s} -1$.

Answer 1

Instead of this, use the fact that $2^{10} \equiv 1 \mod 11$, which is Fermat's little theorem. Now, if $2^s \equiv 1 \mod 11$ for some $1 \leq s \leq 9$, then $s$ must divide $10$.(*) (That is, if you don't know this go below the answer).

However, it is easy to see that $s=1,2,5$ don't work out, since these are easy powers of $2$ to compute. Hence, none of $1,2,...,2^9$ leave remainder $1$ upon division by $10$, and hence $2^r(2^{s-r} - 1)$ cannot be a multiple of $11$ if $0 \leq r < s < 10$.

EDIT : If you did not want to use Fermat's little theorem, then you must make do with the observation that $2^5 \equiv -1 \mod 11$ by inspection, since $2^5 = 32$ is very small, so squaring both sides $2^{10} \equiv (-1)^2 \equiv 1 \mod 11$. Then the above proof works out, since we only needed knowledge about $2^{10}$ to proceed further.

---

(*) Suppose $s$ is the smallest positive number satisfying $2^s \equiv 1 \mod 11$. Then $s \leq 10$. Let $r$ be the remainder when $10$ is divided by $s$. We see that $$qs + r = 10 \implies 1\equiv 2^{10} \equiv (2^{s})^q 2^r \equiv 1^q2^r \equiv 2^r \mod 11$$, so $r < s$ satisfies the proposition. To prevent a contradiction, we must have $r = 0$ i.e. $s$ divides $10$.