Complete Residue System/Examples/Modulo 11/Powers of 2
Jump to navigation
Jump to search
Examples of Complete Residue Systems
- $\set {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512}$
forms a complete residue system modulo $11$.
Proof
We have:
| \(\ds 16\) | \(=\) | \(\ds 1 \times 11 + 5\) | ||||||||||||
| \(\ds \) | \(\equiv\) | \(\ds 5\) | \(\ds \pmod {11}\) | |||||||||||
| \(\ds 32\) | \(=\) | \(\ds 2 \times 11 + 10\) | ||||||||||||
| \(\ds \) | \(\equiv\) | \(\ds 10\) | \(\ds \pmod {11}\) | |||||||||||
| \(\ds 64\) | \(=\) | \(\ds 5 \times 11 + 9\) | ||||||||||||
| \(\ds \) | \(\equiv\) | \(\ds 9\) | \(\ds \pmod {11}\) | |||||||||||
| \(\ds 128\) | \(=\) | \(\ds 11 \times 11 + 7\) | ||||||||||||
| \(\ds \) | \(\equiv\) | \(\ds 7\) | \(\ds \pmod {11}\) | |||||||||||
| \(\ds 256\) | \(=\) | \(\ds 23 \times 11 + 3\) | ||||||||||||
| \(\ds \) | \(\equiv\) | \(\ds 3\) | \(\ds \pmod {11}\) | |||||||||||
| \(\ds 512\) | \(=\) | \(\ds 46 \times 11 + 6\) | ||||||||||||
| \(\ds \) | \(\equiv\) | \(\ds 6\) | \(\ds \pmod {11}\) |
Thus we see that:
- $\set {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512}$
is equivalent to:
- $\set {0, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6}$
The result follows from Initial Segment of Natural Numbers forms Complete Residue System.
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-2}$ Residue Systems: Exercise $1 \ \text {(a)}$