# 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

\(\displaystyle x \bmod 3\) | \(=\) | \(\displaystyle 2\) | |||||||||||

\(\displaystyle x \bmod 5\) | \(=\) | \(\displaystyle 3\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 5 x \bmod 15\) | \(=\) | \(\displaystyle 10\) | Product Distributes over Modulo Operation | |||||||||

\(\displaystyle 3 x \bmod 15\) | \(=\) | \(\displaystyle 9\) |

Hence by definition of congruence by the modulo operation:

\(\displaystyle 5 x\) | \(\equiv\) | \(\displaystyle 10\) | \(\displaystyle \pmod {15}\) | ||||||||||

\(\displaystyle 3 x\) | \(\equiv\) | \(\displaystyle 9\) | \(\displaystyle \pmod {15}\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 2 x\) | \(\equiv\) | \(\displaystyle 1\) | \(\displaystyle \pmod {15}\) | Modulo Subtraction is Well-Defined: $5 x = 3 x$ | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 2 x\) | \(\equiv\) | \(\displaystyle 16\) | \(\displaystyle \pmod {15}\) | Definition of Congruence Modulo Integer | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x\) | \(\equiv\) | \(\displaystyle 8\) | \(\displaystyle \pmod {15}\) | Common Factor Cancelling in Congruence: Corollary | ||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x \bmod 15\) | \(=\) | \(\displaystyle 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$