Modulo Operation/Examples/x mod 3 = 2 and x mod 5 = 3

From ProofWiki
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