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

\(\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