Modulo Operation/Examples/x mod 3 = 2 and x mod 5 = 3
Jump to navigation
Jump to search
Example of use of Modulo Operation
Let $x \bmod 3 = 2$ and $x \bmod 5 = 3$.
Then:
- $x \bmod 15 = 8$
Proof
\(\ds x \bmod 3\) | \(=\) | \(\ds 2\) | ||||||||||||
\(\ds x \bmod 5\) | \(=\) | \(\ds 3\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds 5 x \bmod 15\) | \(=\) | \(\ds 10\) | Product Distributes over Modulo Operation | ||||||||||
\(\ds 3 x \bmod 15\) | \(=\) | \(\ds 9\) |
Hence by definition of congruence by the modulo operation:
\(\ds 5 x\) | \(\equiv\) | \(\ds 10\) | \(\ds \pmod {15}\) | |||||||||||
\(\ds 3 x\) | \(\equiv\) | \(\ds 9\) | \(\ds \pmod {15}\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds 2 x\) | \(\equiv\) | \(\ds 1\) | \(\ds \pmod {15}\) | Modulo Subtraction is Well-Defined: $5 x = 3 x$ | |||||||||
\(\ds \leadsto \ \ \) | \(\ds 2 x\) | \(\equiv\) | \(\ds 16\) | \(\ds \pmod {15}\) | Definition of Congruence Modulo Integer | |||||||||
\(\ds \leadsto \ \ \) | \(\ds x\) | \(\equiv\) | \(\ds 8\) | \(\ds \pmod {15}\) | Common Factor Cancelling in Congruence: Corollary | |||||||||
\(\ds \leadsto \ \ \) | \(\ds x \bmod 15\) | \(=\) | \(\ds 8\) | Definition of Congruence by Modulo Operation |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $14$