User:Rigormath

\cdot centered in mobile view?

Modular arithmetic

For a given positive integer $m$ , two integers, $a$ and $b$ , are said to be congruent modulo $m$ if $m$ divides their difference. This binary relation is denoted by,

a\equiv b{\pmod {m}}.

This is an equivalence relation on the set of integers, $\mathbb {Z}$ , and the equivalence classes are called congruence classes modulo $m$ or residue classes modulo $m$ . Let ${\overline {a}}$ denote the congruence class containing the integer $a$ ,^[1] then

{\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.

A linear congruence is a modular congruence of the form

ax\equiv b{\pmod {m}}.

Unlike linear equations over the reals, linear congruences may have zero, one or several solutions. If $x$ is a solution of a linear congruence then every element in ${\overline {x}}$ is also a solution, so, when speaking of the number of solutions of a linear congruence we are referring to the number of different congruence classes that contain solutions.

If $d$ is the greatest common divisor of $a$ and $m$ then the linear congruence $ax \equiv b (mod m)$ has solutions if and only if $d$ divides $b$ . If $d$ divides $b$ , then there are exactly $d$ solutions.^[2]

A modular multiplicative inverse of an integer $a$ with respect to the modulus $m$ is a solution of the linear congruence

ax\equiv 1{\pmod {m}}.

The previous result says that a solution exists if and only if $gcd(a, m) = 1$ , that is, $a$ and $m$ must be relatively prime (i.e. coprime). Furthermore, when this condition holds, there is exactly one solution, i.e., when it exists, a modular multiplicative inverse is unique:^[3] If $b$ and $b'$ are both modular multiplicative inverses of $a$ respect to the modulus $m$ , then

ab\equiv ab'\equiv 1{\pmod {m}},

therefore

a(b-b')\equiv 0{\pmod {m}}.

If $a \equiv 0 (mod m)$ , then $gcd(a, m) = m$ , and $a$ won't even have a modular multiplicative inverse. Therefore, $b \equiv b' (mod m)$ .

When $ax \equiv 1 (mod m)$ has a solution it is often denoted in this way −

x\equiv a^{-1}{\pmod {m}},

but this can be considered an abuse of notation since it could be misinterpreted as the reciprocal of $a$ (which, contrary to the modular multiplicative inverse, is not an integer except when $a$ is 1 or −1). The notation would be proper if $a$ is interpreted as a token standing for the congruence class ${\overline {a}}$ , as the multiplicative inverse of a congruence class is a congruence class with the multiplication defined in the next section.

Integers modulo $m$

The congruence relation, modulo $m$ , partitions the set of integers into $m$ congruence classes. Operations of addition and multiplication can be defined on these $m$ objects in the following way: To either add or multiply two congruence classes, first pick a representative (in any way) from each class, then perform the usual operation for integers on the two representatives and finally take the congruence class that the result of the integer operation lies in as the result of the operation on the congruence classes. In symbols, these definitions are

{\overline {a}}+{\overline {b}}={\overline {a+b}}

and

{\overline {a}}\cdot {\overline {b}}={\overline {ab}},

where $+$ and $\,\!\cdot$ on the left denote addition and multiplication of congruence classes modulo $m$ . These operations are well-defined, meaning that the end result does not depend on the choices of representatives that were made to obtain the result.

The $m$ congruence classes with these two defined operations form a commutative ring, called the ring of integers modulo $m$ . There are several notations used for these algebraic objects, most often $\mathbb {Z} /m\mathbb {Z}$ or $\mathbb {Z} /m$ , but several elementary texts and application areas use a simplified notation $\mathbb {Z} _{m}$ when confusion with other algebraic objects is unlikely.

The congruence classes of the integers modulo $m$ were traditionally known as residue classes modulo m, reflecting the fact that all the elements of a congruence class have the same remainder (i.e., "residue") upon being divided by $m$ . Any set of $m$ integers selected so that each comes from a different congruence class modulo m is called a complete system of residues modulo $m$ .^[4] The division algorithm shows that the set of integers, ${0, 1, 2, ..., m - 1}$ form a complete system of residues modulo $m$ , known as the least residue system modulo $m$ . In working with arithmetic problems it is sometimes more convenient to work with a complete system of residues and use the language of congruences while at other times the point of view of the congruence classes of the ring $\mathbb {Z} /m\mathbb {Z}$ is more useful.^[5]

Multiplicative group of integers modulo $m$

Not every element of a complete residue system modulo $m$ has a modular multiplicative inverse, for instance, zero does not have one if $m > 1$ . After removing the elements of a complete residue system that are not relatively prime to $m$ , what is left is called a reduced residue system, all of whose elements have modular multiplicative inverses. The number of elements in a reduced residue system is $\phi (m)$ , where $\phi$ is the Euler totient function, i.e., the number of positive integers less than $m$ that are relatively prime to $m$ .

In a general ring with unity not every element has a multiplicative inverse and those that do are called units. As the product of two units is a unit, the units of a ring form a group, the group of units of the ring and often denoted by $R \times$ if $R$ is the name of the ring. The group of units of the ring of integers modulo $m$ is called the multiplicative group of integers modulo $m$ , and it is isomorphic to a reduced residue system. In particular, it has order (size), $\phi (m)$ .

In the case that $m$ is a prime, say $p$ , then $\phi (p)=p-1$ and all the non-zero elements of $\mathbb {Z} /p\mathbb {Z}$ have multiplicative inverses, thus $\mathbb {Z} /p\mathbb {Z}$ is a finite field. In this case, the multiplicative group of integers modulo $p$ form a cyclic group of order $p - 1$ .

^ Other notations are often used, including $[a]$ and $[a] m$ .
^ Ireland & Rosen 1990, p. 32
^ Shoup, Victor (2005), A Computational Introduction to Number Theory and Algebra, Cambridge University Press, Theorem 2.4, p. 15, ISBN 9780521851541
^ Rosen 1993, p. 121
^ Ireland & Rosen 1990, p. 31

[1] Other notations are often used, including $[a]$ and $[a] m$ .

[2] Ireland & Rosen 1990, p. 32

[3] Shoup, Victor (2005), A Computational Introduction to Number Theory and Algebra, Cambridge University Press, Theorem 2.4, p. 15, ISBN 9780521851541

[4] Rosen 1993, p. 121

[5] Ireland & Rosen 1990, p. 31

[1]

[2]

[3]

[4]

[5]

Modular arithmetic

Integers modulo m

Multiplicative group of integers modulo m

Integers modulo $m$

Multiplicative group of integers modulo $m$