Definition:Modulo Multiplication

From ProofWiki
Jump to navigation Jump to search

Definition

Definition 1

Let $m \in \Z$ be an integer.

Let $\Z_m$ be the set of integers modulo $m$:

$\Z_m = \set {\eqclass 0 m, \eqclass 1 m, \ldots, \eqclass {m - 1} m}$

where $\eqclass x m$ is the residue class of $x$ modulo $m$.


The operation of multiplication modulo $m$ is defined on $\Z_m$ as:

$\eqclass a m \times_m \eqclass b m = \eqclass {a b} m$


Definition 2

Let $m \in \Z$ be an integer.

Let $\Z_m$ be the set of integers modulo $m$:

$\Z_m = \set {0, 1, \ldots, m - 1}$


The operation of multiplication modulo $m$ is defined on $\Z_m$ as:

$a \times_m b$ equals the remainder after $a b$ has been divided by $m$.


Definition 3

Let $m \in \Z$ be an integer.

Let $\Z_m$ be the set of integers modulo $m$:

$\Z_m = \set {0, 1, \ldots, m - 1}$


The operation of multiplication modulo $m$ is defined on $\Z_m$ as:

$a \times_m b := a b - k m$

where $k$ is the largest integer such that $k m \le a b$.


Also denoted as

Although the operation of multiplication modulo $m$ is denoted by the symbol $\times_m$, if there is no danger of confusion, the conventional multiplication symbols $\times, \cdot$ etc. are often used instead.

The notation for multiplication of two integers modulo $m$ is not usually $\eqclass a m \times_m \eqclass b m$.

What is more normally seen is $a b \pmod m$.


Cayley Table

Modulo 3

$\begin{array} {r|rrr}

\struct {\Z_3, \times_3} & \eqclass 0 3 & \eqclass 1 3 & \eqclass 2 3 & \\ \hline \eqclass 0 3 & \eqclass 0 3 & \eqclass 0 3 & \eqclass 0 3 \\ \eqclass 1 3 & \eqclass 0 3 & \eqclass 1 3 & \eqclass 2 3 \\ \eqclass 2 3 & \eqclass 0 3 & \eqclass 2 3 & \eqclass 1 3 \\ \end{array}$

which can also be presented:

$\begin{array} {r|rrrrr}

\times_3 & 0 & 1 & 2 \\ \hline 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 \\ 2 & 0 & 2 & 1 \end{array}$


Modulo 4

$\begin{array} {r|rrrrr}

\struct {\Z_4, \times_4} & \eqclass 0 4 & \eqclass 1 4 & \eqclass 2 4 & \eqclass 3 4 \\ \hline \eqclass 0 4 & \eqclass 0 4 & \eqclass 0 4 & \eqclass 0 4 & \eqclass 0 4 \\ \eqclass 1 4 & \eqclass 0 4 & \eqclass 1 4 & \eqclass 2 4 & \eqclass 3 4 \\ \eqclass 2 4 & \eqclass 0 4 & \eqclass 2 4 & \eqclass 0 4 & \eqclass 2 4 \\ \eqclass 3 4 & \eqclass 0 4 & \eqclass 3 4 & \eqclass 2 4 & \eqclass 1 4 \\ \end{array}$

which can also be presented:

$\begin{array} {r|rrrrr}

\times_4 & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 \\ 2 & 0 & 2 & 0 & 2 \\ 3 & 0 & 3 & 2 & 1 \\ \end{array}$


Modulo 5

$\begin{array} {r|rrrrr}

\struct {\Z_5, \times_5} & \eqclass 0 5 & \eqclass 1 5 & \eqclass 2 5 & \eqclass 3 5 & \eqclass 4 5 \\ \hline \eqclass 0 5 & \eqclass 0 5 & \eqclass 0 5 & \eqclass 0 5 & \eqclass 0 5 & \eqclass 0 5 \\ \eqclass 1 5 & \eqclass 0 5 & \eqclass 1 5 & \eqclass 2 5 & \eqclass 3 5 & \eqclass 4 5 \\ \eqclass 2 5 & \eqclass 0 5 & \eqclass 2 5 & \eqclass 4 5 & \eqclass 1 5 & \eqclass 3 5 \\ \eqclass 3 5 & \eqclass 0 5 & \eqclass 3 5 & \eqclass 1 5 & \eqclass 4 5 & \eqclass 2 5 \\ \eqclass 4 5 & \eqclass 0 5 & \eqclass 4 5 & \eqclass 3 5 & \eqclass 2 5 & \eqclass 1 5 \\ \end{array}$

which can also be presented:

$\begin{array} {r|rrrrr}

\times_5 & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 \\ 2 & 0 & 2 & 4 & 1 & 3 \\ 3 & 0 & 3 & 1 & 4 & 2 \\ 4 & 0 & 4 & 3 & 2 & 1 \\ \end{array}$


Modulo 6

$\quad \begin{array} {r|rrrrrr} \struct {\Z_6, \times_6} & \eqclass 0 6 & \eqclass 1 6 & \eqclass 2 6 & \eqclass 3 6 & \eqclass 4 6 & \eqclass 5 6 \\ \hline \eqclass 0 6 & \eqclass 0 6 & \eqclass 0 6 & \eqclass 0 6 & \eqclass 0 6 & \eqclass 0 6 & \eqclass 0 6 \\ \eqclass 1 6 & \eqclass 0 6 & \eqclass 1 6 & \eqclass 2 6 & \eqclass 3 6 & \eqclass 4 6 & \eqclass 5 6 \\ \eqclass 2 6 & \eqclass 0 6 & \eqclass 2 6 & \eqclass 4 6 & \eqclass 0 6 & \eqclass 2 6 & \eqclass 4 6 \\ \eqclass 3 6 & \eqclass 0 6 & \eqclass 3 6 & \eqclass 0 6 & \eqclass 3 6 & \eqclass 0 6 & \eqclass 3 6 \\ \eqclass 4 6 & \eqclass 0 6 & \eqclass 4 6 & \eqclass 2 6 & \eqclass 0 6 & \eqclass 4 6 & \eqclass 2 6 \\ \eqclass 5 6 & \eqclass 0 6 & \eqclass 5 6 & \eqclass 4 6 & \eqclass 3 6 & \eqclass 2 6 & \eqclass 1 6 \end{array}$


Examples

Example: $8 \times 27 \pmod {10}$

\(\ds \paren {8 \times 27} \pmod {10}\) \(=\) \(\ds \paren {18 \times 7} \pmod {10}\)
\(\ds \) \(=\) \(\ds 6 \pmod {10}\)


Also see

  • Results about modulo multiplication can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Modulo_Multiplication&oldid=660844"