Congruence#
KaTeX \(\renewcommand{\c}[1]{\textcolor{#1}}\)
import itertools
Fermat’s reading of Diophantus Arithmetica
proof that no number of the form \(4k + 3\) can be a sum of two squares (Bachet, Descartes)
“When may an integer be expressed as a sum of two squares?” is a natural question in view of the Greeks’ geometric algebra and Pythagoras’ Theorem.
The idea of congruence modulo an integer “was fairly explicit in the work of Fermat and his contemporaries”. The ideas of congruence modulo an integer and congruence classes “occur in Euler’s later works in the mid-eighteenth century, but the notation which we use now was introduced by Gauss in his Disquisitiones Arithmeticae published in 1801, which begins with a thorough treatment of these ideas.”
The ideas of congruence modulo an integer and congruence classes “were implicit in early work in number theory in the sense that if one refers to, say, ‘integers of the form \(4n + 3\)’ then one is implicitly referring to the congruence class \([3]_4\). These notions only became explicit with Euler: as his work in number theory developed, he became increasingly aware that he was working not with numbers, but with certain sets of numbers. However, the Tractatus de Numerorum Doctrina, in which he systematically developed these notions (around 1750), was not published by him, although he did incorporate many of the results in various of his papers. The Tractatus was printed posthumously in 1830 but by then it had been superseded by Gauss’ Disquisitiones Arithmeticae (1801). In that work Gauss went considerably further than Euler had. The notations that we use here for congruence and for congruence classes were introduced by Gauss.”
“A method for finding inverses modulo \(n\) (when they exist) is found in Bachet’s Problèmes plaisants et délectables (1612), but Brahmagupta, who flourished about 628 CE, had already given the general solution.”
Congruence modulo an integer#
\(Definition\)
Let \(n\) be an integer greater than \(1\) and let \(a\) and \(b\) be integers.
\(a\) is congruent to \(b\) mod(ulo) \(n\) if \(a\) and \(b\) have the same remainder when divided by \(n\).
\(a \equiv b \mod n\)
Equivalently: \(a \equiv b \mod n \iff n \mid a - b\).
The condition “\(n\) divides \(a\)” can be written \(a \equiv 0 \mod n\).
Properties of congruence#
Properties of congruence \(\equiv\) are similar to those of equality \(=\).
Let \(a, b, c\) be integers and \(a \equiv b \mod n\).
\( \begin{alignedat}{4} a + c &\equiv b + c &\mod n &\iff n \mid (a + c) - (b + c) &&\iff n \mid a - b + c - c &\iff a \equiv b \mod n \\ a - c &\equiv b - c &\mod n &\iff n \mid (a - c) - (b - c) &&\iff n \mid a - b - c + c &\iff a \equiv b \mod n \\ ca &\equiv cb &\mod n &\iff n \mid ca - cb &&\iff n \mid c(a - b) &\iff a \equiv b \mod n \\ \end{alignedat} \)
A sum of two squares cannot be of the form \(4k + 3\)#
Take any integer \(m\) and square it. What are the possibilities for \(m^2 \mod 4\)?
If an integer \(k\) is the sum of two squares \(k = n^2 + m^2\) then the possibilities for \(k\) are \((0 \,\,\text{or}\,\, 1) + (0 \,\,\text{or}\,\, 1) \mod 4\). In particular, it is impossible for \(k\) to be congruent to \(3\) module \(4\). In other words, a sum of two squares cannot be of the form \(4t + 3\).
\(k \not\equiv 3 \mod 4 \iff 4 \nmid k - 3 \iff k - 3 \ne 4t \iff k \ne 4t + 3\)
\( \begin{aligned} 0 + 0 &= 0 \mod 4 \\ 0 + 1 &= 1 \mod 4 \\ 1 + 0 &= 1 \mod 4 \\ 1 + 1 &= 2 \mod 4 \\ \end{aligned} \)
A sum of three squares cannot be of the form \(8k + 7\)#
Take any integer \(m\) and square it. What are the possibilities for \(m^2 \mod 8\)?
If an integer \(k\) is the sum of three squares \(k = l^2 + n^2 + m^2\) then the possibilities for \(k\) are \((0 \,\,\text{or}\,\, 1 \,\,\text{or}\,\, 4) + (0 \,\,\text{or}\,\, 1 \,\,\text{or}\,\, 4) + (0 \,\,\text{or}\,\, 1 \,\,\text{or}\,\, 4) \mod 8\). In particular, it is impossible for \(k\) to be congruent to \(7\) module \(8\). In other words, a sum of two squares cannot be of the form \(8t + 7\).
\(k \not\equiv 7 \mod 8 \iff 8 \nmid k - 7 \iff k - 7 \ne 8t \iff k \ne 8t + 7\)
\( \begin{aligned} 0 + 0 + 0 &= 0 \mod 8 \\ 0 + 0 + 1 &= 1 \mod 8 \\ 0 + 0 + 4 &= 4 \mod 8 \\ 0 + 1 + 0 &= 1 \mod 8 \\ 0 + 1 + 1 &= 2 \mod 8 \\ 0 + 1 + 4 &= 5 \mod 8 \\ 0 + 4 + 0 &= 4 \mod 8 \\ 0 + 4 + 1 &= 5 \mod 8 \\ 0 + 4 + 4 &= 0 \mod 8 \\ 1 + 0 + 0 &= 1 \mod 8 \\ 1 + 0 + 1 &= 2 \mod 8 \\ 1 + 0 + 4 &= 5 \mod 8 \\ 1 + 1 + 0 &= 2 \mod 8 \\ 1 + 1 + 1 &= 3 \mod 8 \\ 1 + 1 + 4 &= 6 \mod 8 \\ 1 + 4 + 0 &= 5 \mod 8 \\ 1 + 4 + 1 &= 6 \mod 8 \\ 1 + 4 + 4 &= 1 \mod 8 \\ 4 + 0 + 0 &= 4 \mod 8 \\ 4 + 0 + 1 &= 5 \mod 8 \\ 4 + 0 + 4 &= 0 \mod 8 \\ 4 + 1 + 0 &= 5 \mod 8 \\ 4 + 1 + 1 &= 6 \mod 8 \\ 4 + 1 + 4 &= 1 \mod 8 \\ 4 + 4 + 0 &= 0 \mod 8 \\ 4 + 4 + 1 &= 1 \mod 8 \\ 4 + 4 + 4 &= 4 \mod 8 \\ \end{aligned} \)
Congruence Class#
The idea of congruence class “occurs in Euler’s later works in the mid-eighteenth century.”
\(Definition\)
Let \(n\) be an integer greater than \(1\) and let \(a\) be any integer.
The congruence class of \(a\) modulo \(n\) is the set of all integers which are congruent to \(a\) modulo \(n\):
The set of all congruence classes modulo \(n\) is referred to as the set of integers modulo \(n\) and is denoted \(\mathbb{Z}_n\).
Observe that this is a set with \(n\) elements, for there are exactly \(n\) possibilities for the remainder when an integer is divided by \(n\).
By the zero congruence class we mean the congruence class of \(0\) (that is, the congruence class consisting of all multiples of \(n\)).
Note that
Since every element of \(\mathbb{Z}_n\) may be represented in infinitely many ways it is useful to fix a set of standard representatives. By a representative of a congruence class we mean any integer in that class. These are usually taken to be the integers from \(0\) to \(n - 1\). Thus
Congruences#
Equations involving congruence modulo an integer are called congruences.
\(Example\)
What is the solution to the following congruence?
\(2x \equiv 0 \mod 4\)
\( \begin{aligned} 2 \times&& \vdots =&& \vdots &\equiv 0 \mod 4 \\ 2 \times&& -10 =&& -20 &\equiv 0 \mod 4 \\ 2 \times&& - 8 =&& -16 &\equiv 0 \mod 4 \\ 2 \times&& - 6 =&& -12 &\equiv 0 \mod 4 \\ 2 \times&& - 4 =&& - 8 &\equiv 0 \mod 4 \\ 2 \times&& - 2 =&& - 4 &\equiv 0 \mod 4 \\ 2 \times&& 0 =&& 0 &\equiv 0 \mod 4 \\ 2 \times&& 2 =&& 4 &\equiv 0 \mod 4 \\ 2 \times&& 4 =&& 8 &\equiv 0 \mod 4 \\ 2 \times&& 6 =&& 12 &\equiv 0 \mod 4 \\ 2 \times&& 8 =&& 16 &\equiv 0 \mod 4 \\ 2 \times&& 10 =&& 20 &\equiv 0 \mod 4 \\ 2 \times&& \vdots =&& \vdots &\equiv 0 \mod 4 \\ \end{aligned} \)
\(x \in [0]_4 \cup [2]_4 = \{ \dots, -10, -8, -6, -4, -2, 0, 2, 4, 6, 8, 10, \dots \} = \mathbb{E}\)
\(\dots \equiv -8 \equiv -4 \equiv 0 \equiv 4 \equiv 8 \equiv \dotsb \mod 4\)
\([0]_4 = \{ \dots, -8, -4, 0, 4, 8, \dots \}\)
\(\dots \equiv -10 \equiv -6 \equiv -2 \equiv 2 \equiv 6 \equiv 10 \equiv \dotsb \mod 4\)
\([2]_4 = \{ \dots, -10, -6, -2, 2, 6, 10, \dots \}\)
The solutions to the congruence \(2x \equiv 0 \mod 4\) are the congruence classes \([0]_4\) and \([2]_4\).
Congruence Class Arithmetic#
Addition and Multiplication#
\(\mathbb{Z}_n\) inherits the arithmetic operations of \(\mathbb{Z}\).
\(Definition\)
Let \(n\) be an integer greater than \(1\) and let \(a\) and \(b\) be integers.
Then the sum and product of the congruence classes of \(a\) and \(b\) are defined as follows:
Additive Associativity#
\(([a]_n + [b]_n) + [c]_n = [a + b]_n + [c]_n = [(a + b) + c]_n = [a + (b + c)]_n = [a]_n + [b + c]_n = [a]_n + ([b]_n + [c]_n)\)
Additive Commutativity#
\([a]_n + [b]_n = [a + b]_n = [b + a]_n = [b]_n + [a]_n\)
Multiplicative Associativity#
\(([a]_n [b]_n) [c]_n = [ab]_n [c]_n = [(ab)c]_n = [a(bc)]_n = [a]_n [bc]_n = [a]_n ([b]_n [c]_n)\)
Multiplicative Commutativity#
\([a]_n [b]_n = [ab]_n = [ba]_n = [b]_n [a]_n\)
More on congruence class arithmetic#
\(Theorem\) [Humphreys & Prest 1.4.1 pp. 40-41]
Let \(n\) be an integer greater than \(1\) and let \(a, b, c\) be integers.
Let \([a]_n = [c]_n\).
Then(i) \([a + b]_n = [c + b]_n\)
(ii) \([ab]_n = [cb]_n\)
\(Proof\) [Humphreys & Prest pp. 41]
(i)
\([a]_n = [c]_n \iff c \equiv a \mod n \iff n \mid c - a \iff \exists k \in \mathbb{Z} \,\, [\,\, nk = c - a \,\,]\)
\(\textcolor{green}{[c + b]_n} = [a + b + nk]_n = [a + b]_n + [nk]_n = \textcolor{green}{[a + b]_n}\) by the definition of congruence class as the set of integers that share a common remainder when divided by \(n\)(ii)
\(\textcolor{green}{[cb]_n} = [(a + kn)b]_n = [ab + nkb]_n = [ab]_n + [nkb]_n = \textcolor{green}{[ab]_n}\) by the definition of congruence class as the set of integers that share a common remainder when divided by \(n\)
\(\blacksquare\)
By symmetry we can replace \(b\) by an element \(d\) in the same class as \(b\).
\(Corollary\) [Humphreys & Prest 1.4.2 pp. 41-42]
If \([a]_n = [c]_n\) and \([b]_n = [d]_n\) then
(i) \([a + b]_n = [c + d]_n\)
(ii) \([ab]_n = [cd]_n\)Therefore we may write the following without ambiguity.
\([a]_n + [b]_n = [a + b]_n\)
\([a]_n [b]_n = [ab]_n\)
\(Example\) [Humphreys & Prest pp. 42]
Show that \(11\) divides \(10! + 1\).
\(11 \mid 10! + 1 \iff 10! \equiv -1 \mod 11\)
\(4! = 4 \times 3 \times 2 = 24 \equiv 2 \mod 11\)
\(6! = 6 \times 5 \times 4! \equiv 6 \times 5 \times 2 = 60 \mod 11\)
\(60 \equiv 5 \mod 11\)
\(7! = 7 \times 6! \equiv 7 \times 5 = 35 \mod 11\)
\(35 \equiv 2 \mod 11\)
\(8! = 8 \times 7! \equiv 8 \times 2 = 16 \mod 11\)
\(16 \equiv 5 \mod 11\)
\(10! = 10 \times 9 \times 8! \equiv 10 \times 9 \times 5 \equiv (-1) \times (-2) \times 5 = 10 \mod 11\)
\(10! + 1 \equiv 10 + 1 \equiv 0 \mod 11\)
\(10! + 1 \equiv 0 \mod 11 \iff 11 \mid 10! + 1\)
\(Example\) [Humphreys & Prest pp. 42]
Find the standard representative of \(([13]_{18})^3\).
\(([13]_{18})^3 = [13]_{18} \times [13]_{18} \times [13]_{18} = [13 \times 13 \times 13]_{18} = [13^3]_{18}\)
\([13]_{18} \iff 13 \equiv -5 \mod 18 \iff 13^3 \equiv (-5)^3 = 25 \times (-5) \equiv 7 \times (-5) = -35 \equiv 1 \mod 18\)
\(([13]_{18})^3 = [1]_{18}\)
Inverses and Zero-Divisors#
\(Definition\) [Humphreys & Prest pp. 43]
Let \(n\) be an integer greater than \(1\) and let \(a\) be an integer.
We say that \([a]_n\) is invertible (or \([a]_n\) is invertible modulo \(n\)) if there is an integer \(b\) s.t. \([a]_n [b]_n = [1]_n\) (that is, s.t. \(ab \equiv 1 \mod n\)), in which case \([b]_n\) is the inverse of \([a]_n\) and we write \([b]_n = [a]_n^{-1}\).
We say that a non-zero congruence class \([a]_n\) is a zero-divisor if there exists an integer \(b\) with \([b]_n \ne [0]_n\) and \([a]_n [b]_n = [0]_n\) (in which case \([b]_n\) is also a zero-divisor).
Inverses and GCD#
\(Theorem\) [Humphreys & Prest 1.4.3 pp. 43]
Let \(n\) be an integer greater than \(1\) and let \(a\) be an integer.
Then \([a]_n\) has an inverse iff the greatest common divisor of \(a\) and \(n\) is \(1\).
In fact, if \(r\) and \(s\) are integers s.t. \(ar + ns = 1\) then the inverse of \([a]_n\) is \([r]_n\).
\(Proof\) [Humphreys & Prest pp. 43]
If \([a]_n\) has an inverse then \(gcd(a, n) = 1\).
Let \([a]_n\) have an inverse \([k]_n\).
\([ak]_n = [1]_n \iff ak \equiv 1 \mod n \iff n \mid ak - 1 \iff \exists t \in \mathbb{Z} \,\, [\,\, nt = ak - 1 \,\,] \iff ak - nt = 1\)
\(\therefore gcd(a, n) = 1\).If \(gcd(a, n) = 1\) then \([a]_n\) has an inverse.
Let \(gcd(a, n) = 1\).
Then there are integers \(r\) and \(s\) s.t. \(ar + ns = 1\).
\(ar + ns = 1 \iff ar - 1 = -ns \iff n \mid ar - 1 \iff ar \equiv 1 \mod n \iff [ar]_n = [1]_n\)
\(\therefore [a]_n\) has an inverse.
\(\blacksquare\)
If the equation \(ar + ns = 1\) is reduced modulo \(n\) then because \(n\) becomes \(0\) the term \(ns\) disappears and we are left with the equation \([ar]_n = [1]_n\); that is, \([a]_n [r]_n = [1]_n\).
\(Example\)
\( \begin{aligned} 1 &= ar + ns && \iff ar - 1 = n \times (-s) && \iff n \mid ar - 1 && \iff ar \equiv 1 \mod n && \iff [ar]_n = [1]_n \\ 1 &= 391 \cdot 118 + 507 \cdot (-91) && \iff 391 \cdot 118 - 1 = 507 \cdot 91 && \iff 507 \mid 391 \cdot 118 - 1 && \iff 391 \cdot 118 \equiv 1 \mod 507 && \iff [391 \cdot 118]_{507} = [1]_{507} \\ 1 &= 391 \cdot 118 + 91 \cdot (-507) && \iff 391 \cdot 118 - 1 = 91 \cdot 507 && \iff 91 \mid 391 \cdot 118 - 1 && \iff 391 \cdot 118 \equiv 1 \mod 91 && \iff [391 \cdot 118]_{91} = [1]_{91} \\ 1 &= (-91) \cdot 507 + 391 \cdot 118 && \iff (-91) \cdot 507 - 1 = 391 \cdot (-118) && \iff 391 \mid (-91) \cdot 507 - 1 && \iff (-91) \cdot 507 \equiv 1 \mod 391 && \iff [(-91) \cdot 507]_{391} = [1]_{391} \\ 1 &= (-91) \cdot 507 + 118 \cdot 391 && \iff (-91) \cdot 507 - 1 = 118 \cdot (-391) && \iff 118 \mid (-91) \cdot 507 - 1 && \iff (-91) \cdot 507 \equiv 1 \mod 118 && \iff [(-91) \cdot 507]_{118} = [1]_{118} \\ \end{aligned} \)
print(391 * 118 % 507)
print(391 * 118 % 91)
print(-91 * 507 % 391)
print(-91 * 507 % 118)
1
1
1
1
\(Example\)
Let \(a = 215\) and \(n = 795\).
\( \begin{aligned} 795 &= 3 \times 215 + 150 \\ 215 &= 1 \times 150 + 65 \\ 150 &= 2 \times 65 + 20 \\ 65 &= 3 \times 20 + 5 \\ 20 &= 4 \times 5 + 0 \\ \end{aligned} \)
\(gcd(215, 795) = 5 \iff 5 = 215r + 795s \iff 215r - 5 = 795 \times (-s) \iff 795 \mid 215r - 5 \iff 215r \equiv 5 \mod 795 \iff [215r]_{795} = [5]_{795}\)
\(215 \mod 795\) has no inverse.
for i in range(int(1e6)):
if 215 * i % 795 == 1:
print(i)
\(Example\)
Let \(a = 23\) and \(n = 73\).
\( \left( \begin{array}{cc|c} 1 & 0 & 73 \\ 0 & 1 & 23 \\ \end{array} \right) \underset{r_1 \leftarrow r_1 - 3r_2}{\to} \left( \begin{array}{cc|c} 1 & -3 & 4 \\ 0 & 1 & 23 \\ \end{array} \right) \underset{r_2 \leftarrow r_2 - 5r_1}{\to} \left( \begin{array}{cc|c} 1 & -3 & 4 \\ -5 & 16 & 3 \\ \end{array} \right) \underset{r_1 \leftarrow r_1 - r_2}{\to} \left( \begin{array}{cc|c} 6 & -19 & 1 \\ -5 & 16 & 3 \\ \end{array} \right) \)
\(6 \cdot 73 + (-19) \cdot 23 = 1 \implies [6 \cdot 73]_{73} + [(-19) \cdot 23]_{73} = [1]_{73} \implies [(-19) \cdot 23]_{73} = [1]_{73}\)
\(-19 \equiv 54 \mod 73 \implies [23]_{73}^{-1} = [54]_{73}\)
\(Example\)
\([8]_{11}^{-1} = \,\, ? \iff [8r]_{11} = [1]_{11} \iff 8r \equiv 1 \mod 11 \iff 11s = 8r - 1 \iff r = \frac{11(s = 5) + 1}{8} = 7\)
\([8]_{11}^{-1} = [7]_{11}\)
\([11]_{20}^{-1} = \,\, ? \iff [11r]_{20} = [1]_{20} \iff 11r \equiv 1 \mod 20 \iff 20s = 11r - 1 \iff r = \frac{20(s = 6) + 1}{11} = 11\)
\([11]_{20}^{-1} = [11]_{20}\)
\(Corollary\) [Humphreys & Prest 1.4.4 pp. 45]
Let \(n\) be an integer greater than \(1\) and let \(a, b, c\) be integers.
If \(n\) and \(c\) are relatively prime and if \(ac \equiv bc \mod n\) then \(a \equiv b \mod n\).
\(Proof\) [Humphreys & Prest pp. 46]
\(ac \equiv bc \mod n \iff [ac]_n = [bc]_n \iff [a]_n [c]_n = [b]_n [c]_n\).
\([c]_n^{-1}\) exists since \(c\) and \(n\) are relatively prime.
\([a]_n [c]_n = [b]_n [c]_n \iff [a]_n [c]_n [c]_n^{-1} = [b]_n [c]_n [c]_n^{-1} \iff [a]_n [1]_n = [b]_n [1]_n \iff [a]_n = [b]_n \iff a \equiv b \mod n\)
\(\blacksquare\)
\(Corollary\) [Humphreys & Prest 1.4.5 pp. 46]
Let \(n\) be an integer greater than \(1\).
Then each non-zero element of \(\mathbb{Z}_n\) is either invertible or a zero-divisor, but not both.
\(Proof\) [Humphreys & Prest pp. 46]
Let it be the case that \([a]_n\) is not invertible.
Then \(gcd(a, n) = d \gt 1\).
\(d \mid a \iff a = kd\) for some integer \(k\)
\(d \mid n \iff n = td\) for some integer \(t\) where \(0 \lt t \lt n\).
\(a = kd \iff at = ktd = kn \iff n \mid at \iff at \equiv 0 \mod n \iff [at]_n = [0]_n \iff [a]_n [t]_n = [0]_n\)
\(\therefore [a]_n\) is a zero-divisor since \([t]_n \ne [0]_n\)Let it be the case that \([a]_n\) is invertible.
\([a]_n [b]_n = [0]_n \iff [a]_n [a]_n^{-1} [b]_n = [0]_n [a]_n^{-1} \iff [b]_n = [0]_n\)
\(\therefore [a]_n\) is not a zero-divisor since \([b]_n = [0]_n\).
\(\blacksquare\)
This result was given by Euler in essentially this form.
\(Corollary\) [Humphreys & Prest 1.4.6 pp. 47]
Let \(p\) be prime.
Then every non-zero element of \(\mathbb{Z}_p\) is invertible.
\(Proof\) [Humphreys & Prest pp. 47]
Let \([a]_p\) be non-zero.
\([a]_p \ne [0]_p \iff a \not\equiv 0 \mod p \iff p \nmid a \iff gcd(a, p) = 1\)
\(\therefore [a]_p^{-1}\).
The set of invertible congruence class modulo an integer#
\(Definition\) [Humphreys & Prest pp. 47]
Let \(n\) be an integer greater than \(1\).
We denote by \(\mathbb{Z}_n^*\) (or \(G_n\)) the set of invertible congruence classes of \(\mathbb{Z}_n\).
\([a]_n \in \mathbb{Z}_n^* \iff gcd(a, n) = 1\)
\(Theorem\) [Humphreys & Prest 1.4.7 pp. 47]
Let \(n\) be an integer greater than \(1\).
The product of any two elements of \(\mathbb{Z}_n^*\) is in \(\mathbb{Z}_n^*\).
This theorem may be extended by induction to the statement that the product of any finite number of, possibly repeated, elements of \(\mathbb{Z}_n^*\) lies in \(\mathbb{Z}_n^*\).
If \(a\) is any member of \(\mathbb{Z}_n^*\) then every positive power \(a^k\) is in \(\mathbb{Z}_n^*\).
It is easy to show by induction that the inverse of \(a^k\) is \((a^{-1})^k\) which is denoted \(a^{-k}\).
Base Case
The inverse of \(a^1\) is \((a^{-1})^1 = a^{-1}\).
Induction Step
Induction Hypothesis: Let the inverse of \(a^k\) be \((a^{-1})^k = a^{-k}\).
\(Proof\) [Humphreys & Prest pp. 47]
Let it be the case that \([a]_n, [b]_n \in \mathbb{Z}_n^*\).
Then \(gcd(a, n) = gcd(b, n) = 1\).
Assume that \(p \mid ab\) and \(p \mid n\) for some prime \(p\).
\(p \mid ab \implies ((p \mid a) \lor (p \mid b))\). \(Contradiction!\)
\(\therefore gcd(ab, n) = 1\).
\(\blacksquare\)
\(\mathbb{Z}_n\)#
The entry in the intersection of the \(a\)-row and \(b\)-column is \([a]_n + [b]_n\) or \([a]_n \times [b]_n\)
\(\mathbb{Z}_2\)#
\( \begin{aligned} n &= 2 \\ \mathbb{Z}_2 &= \{ [0]_2, [1]_2 \} \\ \mathbb{Z}_2^* &= \{ [1]_2 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_2 &= \mathbb{E} && = \{ \dots, && -4, && -2, && 0, && 2, && 4, && \dots \} \\ [1]_2 &= \mathbb{O} && = \{ \dots, && -3, && -1, && && 1, && 3, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 2
c0 = [-4, -2, 0, 2, 4]
c1 = [-3, -1, 1, 3]
congruence_class = []
for i, j in list(itertools.product(c1, c1, repeat = 1)):
congruence_class.append(i*j % n)
print(f'1 x 1 : {congruence_class}')
1 x 1 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_3\)#
\( \begin{aligned} n &= 3 \\ \mathbb{Z}_3 &= \{ [0]_3, [1]_3, [2]_3 \} \\ \mathbb{Z}_3^* &= \{ [1]_3, [2]_3 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_3 &= \{ \dots, && -6, && -3, && 0, && 3, && 6, && \dots \} \\ [1]_3 &= \{ \dots, && -5, && -2, && 1, && 4, && 7, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_3 &= \{ \dots, && -4, && -1, && 2, && 5, && 8, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 3
c0 = [-6, -3, 0, 3, 6]
c1 = [-5, -2, 1, 4, 7]
c2 = [-4, -1, 2, 5, 8]
congruence_class = []
for i, j in list(itertools.product(c1, c1, repeat = 1)):
congruence_class.append(i*j % n)
print(f'1 x 1 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c2, c2, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 2 : {congruence_class}')
1 x 1 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2 x 2 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_4\)#
\( \begin{aligned} n &= 4 \\ \mathbb{Z}_4 &= \{ [0]_4, [1]_4, [2]_4, [3]_4 \} \\ \mathbb{Z}_4^* &= \{ [1]_4, [3]_4 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_4 &= \{ \dots, && -8, && -4, && 0, && 4, && 8, && \dots \} \\ [1]_4 &= \{ \dots, && -7, && -3, && 1, && 5, && 9, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_4 &= \{ \dots, && -6, && -2, && 2, && 6, && 10, && \dots \} && \text{zero-divisor} && \text{self-divisor} \\ [3]_4 &= \{ \dots, && -5, && -1, && 3, && 7, && 11, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 4
c0 = [-8, -4, 0, 4, 8]
c1 = [-7, -3, 1, 5, 9]
c2 = [-6, -2, 2, 6, 10]
c3 = [-5, -1, 3, 7, 11]
congruence_class = []
for i, j in list(itertools.product(c2, c2, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 2 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c3, c3, repeat = 1)):
congruence_class.append(i*j % n)
print(f'3 x 3 : {congruence_class}')
2 x 2 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 x 3 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_5\)#
\( \begin{aligned} n &= 5 \\ \mathbb{Z}_5 &= \{ [0]_5, [1]_5, [2]_5, [3]_5, [4]_5 \} \\ \mathbb{Z}_5^* &= \{ [1]_5, [2]_5, [3]_5, [4]_5 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_5 &= \{ \dots, && -10, && -5, && 0, && 5, && 10, && \dots \} \\ [1]_5 &= \{ \dots, && -9, && -4, && 1, && 6, && 11, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_5 &= \{ \dots, && -8, && -3, && 2, && 7, && 12, && \dots \} && \text{invertible} && [3]_5 \\ [3]_5 &= \{ \dots, && -7, && -2, && 3, && 8, && 13, && \dots \} && \text{invertible} && [2]_5 \\ [4]_5 &= \{ \dots, && -6, && -1, && 4, && 9, && 14, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 5
c0 = [-10, -5, 0, 5, 10]
c1 = [ -9, -4, 1, 6, 11]
c2 = [ -8, -3, 2, 7, 12]
c3 = [ -7, -2, 3, 8, 13]
c4 = [ -6, -1, 4, 9, 14]
congruence_class = []
for i, j in list(itertools.product(c2, c3, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 3 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c4, c4, repeat = 1)):
congruence_class.append(i*j % n)
print(f'4 x 4 : {congruence_class}')
2 x 3 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
4 x 4 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_6\)#
\( \begin{aligned} n &= 6 \\ \mathbb{Z}_6 &= \{ [0]_6, [1]_6, [2]_6, [3]_6, [4]_6, [5]_6 \} \\ \mathbb{Z}_6^* &= \{ [1]_6, [5]_6 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_6 &= \{ \dots, && -12, && -6, && 0, && 6, && 12, && \dots \} \\ [1]_6 &= \{ \dots, && -11, && -5, && 1, && 7, && 13, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_6 &= \{ \dots, && -10, && -4, && 2, && 8, && 14, && \dots \} && \text{zero-divisor} && [3]_6 \\ [3]_6 &= \{ \dots, && -9, && -3, && 3, && 9, && 15, && \dots \} && \text{zero-divisor} && [2]_6, [4]_6 \\ [4]_6 &= \{ \dots, && -8, && -2, && 4, && 10, && 16, && \dots \} && \text{zero-divisor} && [3]_6 \\ [5]_6 &= \{ \dots, && -7, && -1, && 5, && 11, && 17, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 6
c0 = [-12, -6, 0, 6, 12]
c1 = [-11, -5, 1, 7, 13]
c2 = [-10, -4, 2, 8, 14]
c3 = [ -9, -3, 3, 9, 15]
c4 = [ -8, -2, 4, 10, 16]
c5 = [ -7, -1, 5, 11, 17]
congruence_class = []
for i, j in list(itertools.product(c2, c3, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 3 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c3, c4, repeat = 1)):
congruence_class.append(i*j % n)
print(f'3 x 4 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c5, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'5 x 5 : {congruence_class}')
2 x 3 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 x 4 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5 x 5 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_7\)#
\( \begin{aligned} n &= 7 \\ \mathbb{Z}_7 &= \{ [0]_7, [1]_7, [2]_7, [3]_7, [4]_7, [5]_7, [6]_7 \} \\ \mathbb{Z}_7^* &= \{ [1]_7, [2]_7, [3]_7, [4]_7, [5]_7, [6]_7 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_7 &= \{ \dots, && -14, && -7, && 0, && 7, && 14, && \dots \} \\ [1]_7 &= \{ \dots, && -13, && -6, && 1, && 8, && 15, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_7 &= \{ \dots, && -12, && -5, && 2, && 9, && 16, && \dots \} && \text{invertible} && [4]_7 \\ [3]_7 &= \{ \dots, && -11, && -4, && 3, && 10, && 17, && \dots \} && \text{invertible} && [5]_7 \\ [4]_7 &= \{ \dots, && -10, && -3, && 4, && 11, && 18, && \dots \} && \text{invertible} && [2]_7 \\ [5]_7 &= \{ \dots, && -9, && -2, && 5, && 12, && 19, && \dots \} && \text{invertible} && [3]_7 \\ [6]_7 &= \{ \dots, && -8, && -1, && 6, && 13, && 20, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 7
c0 = [-14, -7, 0, 7, 14]
c1 = [-13, -6, 1, 8, 15]
c2 = [-12, -5, 2, 9, 16]
c3 = [-11, -4, 3, 10, 17]
c4 = [-10, -3, 4, 11, 18]
c5 = [ -9, -2, 5, 12, 19]
c6 = [ -8, -1, 6, 13, 20]
congruence_class = []
for i, j in list(itertools.product(c2, c4, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 4 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c3, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'3 x 5 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c6, c6, repeat = 1)):
congruence_class.append(i*j % n)
print(f'6 x 6 : {congruence_class}')
2 x 4 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
3 x 5 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
6 x 6 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_8\)#
\( \begin{aligned} n &= 8 \\ \mathbb{Z}_8 &= \{ [0]_8, [1]_8, [2]_8, [3]_8, [4]_8, [5]_8, [6]_8, [7]_8 \} \\ \mathbb{Z}_8^* &= \{ [1]_8, [3]_8, [5]_8, [7]_8 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_8 &= \{ \dots, && -16, && -8, && 0, && 8, && 16, && \dots \} \\ [1]_8 &= \{ \dots, && -15, && -7, && 1, && 9, && 17, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_8 &= \{ \dots, && -14, && -6, && 2, && 10, && 18, && \dots \} && \text{zero-divisor} && [4]_8 \\ [3]_8 &= \{ \dots, && -13, && -5, && 3, && 11, && 19, && \dots \} && \text{invertible} && \text{self-inverse} \\ [4]_8 &= \{ \dots, && -12, && -4, && 4, && 12, && 20, && \dots \} && \text{zero-divisor} && [2]_8, [4]_8, [6]_8 \,\,\text{(self-divisor)} \\ [5]_8 &= \{ \dots, && -11, && -3, && 5, && 13, && 21, && \dots \} && \text{invertible} && \text{self-inverse} \\ [6]_8 &= \{ \dots, && -10, && -2, && 6, && 14, && 22, && \dots \} && \text{zero-divisor} && [4]_8 \\ [7]_8 &= \{ \dots, && -9, && -1, && 7, && 15, && 23, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 8
c0 = [-16, -8, 0, 8, 16]
c1 = [-15, -7, 1, 9, 17]
c2 = [-14, -6, 2, 10, 18]
c3 = [-13, -5, 3, 11, 19]
c4 = [-12, -4, 4, 12, 20]
c5 = [-11, -3, 5, 13, 21]
c6 = [-10, -2, 6, 14, 22]
c7 = [ -9, -1, 7, 15, 23]
congruence_class = []
for i, j in list(itertools.product(c2, c4, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 4 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c3, c3, repeat = 1)):
congruence_class.append(i*j % n)
print(f'3 x 3 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c4, c4, repeat = 1)):
congruence_class.append(i*j % n)
print(f'4 x 4 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c4, c6, repeat = 1)):
congruence_class.append(i*j % n)
print(f'4 x 6 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c5, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'5 x 5 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c7, c7, repeat = 1)):
congruence_class.append(i*j % n)
print(f'7 x 7 : {congruence_class}')
2 x 4 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 x 3 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
4 x 4 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4 x 6 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5 x 5 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
7 x 7 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_9\)#
\( \begin{aligned} n &= 9 \\ \mathbb{Z}_9 &= \{ [0]_9, [1]_9, [2]_9, [3]_9, [4]_9, [5]_9, [6]_9, [7]_9, [8]_9 \} \\ \mathbb{Z}_9^* &= \{ [1]_9, [2]_9, [4]_9, [5]_9, [7]_9, [8]_9 \} \\ \end{aligned} \)
\( \begin{aligned} [0]_9 &= \{ \dots, && -18, && -9, && 0, && 9, && 18, && \dots \} \\ [1]_9 &= \{ \dots, && -17, && -8, && 1, && 10, && 19, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_9 &= \{ \dots, && -16, && -7, && 2, && 11, && 20, && \dots \} && \text{invertible} && [5]_9 \\ [3]_9 &= \{ \dots, && -15, && -6, && 3, && 12, && 21, && \dots \} && \text{zero-divisor} && [3]_9, [6]_9 \,\,\text{(self-divisor)} \\ [4]_9 &= \{ \dots, && -14, && -5, && 4, && 13, && 22, && \dots \} && \text{invertible} && [7]_9 \\ [5]_9 &= \{ \dots, && -13, && -4, && 5, && 14, && 23, && \dots \} && \text{invertible} && [2]_9 \\ [6]_9 &= \{ \dots, && -12, && -3, && 6, && 15, && 24, && \dots \} && \text{zero-divisor} && [3]_9, [6]_9 \,\,\text{(self-divisor)} \\ [7]_9 &= \{ \dots, && -11, && -2, && 7, && 16, && 25, && \dots \} && \text{invertible} && [4]_9 \\ [8]_9 &= \{ \dots, && -10, && -1, && 8, && 17, && 26, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 9
c0 = [-18, -9, 0, 9, 18]
c1 = [-17, -8, 1, 10, 19]
c2 = [-16, -7, 2, 11, 20]
c3 = [-15, -6, 3, 12, 21]
c4 = [-14, -5, 4, 13, 22]
c5 = [-13, -4, 5, 14, 23]
c6 = [-12, -3, 6, 15, 24]
c7 = [-11, -2, 7, 16, 25]
c8 = [-10, -1, 8, 17, 26]
congruence_class = []
for i, j in list(itertools.product(c2, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 5 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c3, c3, repeat = 1)):
congruence_class.append(i*j % n)
print(f'3 x 3 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c3, c6, repeat = 1)):
congruence_class.append(i*j % n)
print(f'3 x 6 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c4, c7, repeat = 1)):
congruence_class.append(i*j % n)
print(f'4 x 7 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c6, c6, repeat = 1)):
congruence_class.append(i*j % n)
print(f'6 x 6 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c8, c8, repeat = 1)):
congruence_class.append(i*j % n)
print(f'8 x 8 : {congruence_class}')
2 x 5 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
3 x 3 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 x 6 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4 x 7 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
6 x 6 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
8 x 8 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_{10}\)#
\( \begin{aligned} n &= 10 \\ \mathbb{Z}_{10} &= \{ [0]_{10}, [1]_{10}, [2]_{10}, [3]_{10}, [4]_{10}, [5]_{10}, [6]_{10}, [7]_{10}, [8]_{10}, [9]_{10} \} \\ \mathbb{Z}_{10}^* &= \{ [1]_{10}, [3]_{10}, [7]_{10}, [9]_{10} \} \\ \end{aligned} \)
\( \begin{aligned} [0]_{10} &= \{ \dots, && -20, && -10, && 0, && 10, && 20, && \dots \} \\ [1]_{10} &= \{ \dots, && -19, && -9, && 1, && 11, && 21, && \dots \} && \text{invertible} && \text{self-inverse} \\ [2]_{10} &= \{ \dots, && -18, && -8, && 2, && 12, && 22, && \dots \} && \text{zero-divisor} && [5]_{10} \\ [3]_{10} &= \{ \dots, && -17, && -7, && 3, && 13, && 23, && \dots \} && \text{invertible} && [7]_{10} \\ [4]_{10} &= \{ \dots, && -16, && -6, && 4, && 14, && 24, && \dots \} && \text{zero-divisor} && [5]_{10} \\ [5]_{10} &= \{ \dots, && -15, && -5, && 5, && 15, && 25, && \dots \} && \text{zero-divisor} && [2]_{10}, [4]_{10}, [6]_{10}, [8]_{10} \\ [6]_{10} &= \{ \dots, && -14, && -4, && 6, && 16, && 26, && \dots \} && \text{zero-divisor} && [5]_{10} \\ [7]_{10} &= \{ \dots, && -13, && -3, && 7, && 17, && 27, && \dots \} && \text{invertible} && [3]_{10} \\ [8]_{10} &= \{ \dots, && -12, && -2, && 8, && 18, && 28, && \dots \} && \text{zero-divisor} && [5]_{10} \\ [9]_{10} &= \{ \dots, && -11, && -1, && 9, && 19, && 29, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
n = 10
c0 = [-20, -10, 0, 10, 20]
c1 = [-19, -9, 1, 11, 21]
c2 = [-18, -8, 2, 12, 22]
c3 = [-17, -7, 3, 13, 23]
c4 = [-16, -6, 4, 14, 24]
c5 = [-15, -5, 5, 15, 25]
c6 = [-14, -4, 6, 16, 26]
c7 = [-13, -3, 7, 17, 27]
c8 = [-12, -2, 8, 18, 28]
c9 = [-11, -1, 9, 19, 29]
congruence_class = []
for i, j in list(itertools.product(c2, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'2 x 5 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c3, c7, repeat = 1)):
congruence_class.append(i*j % n)
print(f'3 x 7 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c4, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'4 x 5 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c6, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'6 x 5 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c8, c5, repeat = 1)):
congruence_class.append(i*j % n)
print(f'8 x 5 : {congruence_class}')
congruence_class = []
for i, j in list(itertools.product(c9, c9, repeat = 1)):
congruence_class.append(i*j % n)
print(f'9 x 9 : {congruence_class}')
2 x 5 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3 x 7 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
4 x 5 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
6 x 5 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
8 x 5 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
9 x 9 : [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
\(\mathbb{Z}_{11}\)#
\( \begin{aligned} n &= 11 \\ \mathbb{Z}_{11} &= \{ [0]_{11}, [1]_{11}, [2]_{11}, [3]_{11}, [4]_{11}, [5]_{11}, [6]_{11}, [7]_{11}, [8]_{11}, [9]_{11}, [10]_{11} \} \\ \end{aligned} \)
\( \begin{aligned} [ 0]_{11} &= \{ \dots, && -22, && -11, && 0, && 11, && 22, && \dots \} \\ [ 1]_{11} &= \{ \dots, && -21, && -10, && 1, && 12, && 23, && \dots \} && \text{invertible} && \text{self-inverse} \\ [ 2]_{11} &= \{ \dots, && -20, && -9, && 2, && 13, && 24, && \dots \} && \text{invertible} && \\ [ 3]_{11} &= \{ \dots, && -19, && -8, && 3, && 14, && 25, && \dots \} && \text{invertible} && \\ [ 4]_{11} &= \{ \dots, && -18, && -7, && 4, && 15, && 26, && \dots \} && \text{invertible} && \\ [ 5]_{11} &= \{ \dots, && -17, && -6, && 5, && 16, && 27, && \dots \} && \text{invertible} && \\ [ 6]_{11} &= \{ \dots, && -16, && -5, && 6, && 17, && 28, && \dots \} && \text{invertible} && \\ [ 7]_{11} &= \{ \dots, && -15, && -4, && 7, && 18, && 29, && \dots \} && \text{invertible} && \\ [ 8]_{11} &= \{ \dots, && -14, && -3, && 8, && 19, && 30, && \dots \} && \text{invertible} && \\ [ 9]_{11} &= \{ \dots, && -13, && -2, && 9, && 20, && 31, && \dots \} && \text{invertible} && \\ [10]_{11} &= \{ \dots, && -12, && -1, && 10, && 21, && 32, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
\(\mathbb{Z}_{12}\)#
\( \begin{aligned} n &= 12 \\ \mathbb{Z}_{12} &= \{ [0]_{12}, [1]_{12}, [2]_{12}, [3]_{12}, [4]_{12}, [5]_{12}, [6]_{12}, [7]_{12}, [8]_{12}, [9]_{12}, [10]_{12}, [11]_{12} \} \\ \end{aligned} \)
\( \begin{aligned} [ 0]_{12} &= \{ \dots, && -24, && -12, && 0, && 12, && 24, && \dots \} \\ [ 1]_{12} &= \{ \dots, && -23, && -11, && 1, && 13, && 25, && \dots \} && \text{invertible} && \text{self-inverse} \\ [ 2]_{12} &= \{ \dots, && -22, && -10, && 2, && 14, && 26, && \dots \} && \text{zero-divisor} && \\ [ 3]_{12} &= \{ \dots, && -21, && -9, && 3, && 15, && 27, && \dots \} && \text{zero-divisor} && \\ [ 4]_{12} &= \{ \dots, && -20, && -8, && 4, && 16, && 28, && \dots \} && \text{zero-divisor} && \\ [ 5]_{12} &= \{ \dots, && -19, && -7, && 5, && 17, && 29, && \dots \} && \text{invertible} && \\ [ 6]_{12} &= \{ \dots, && -18, && -6, && 6, && 18, && 30, && \dots \} && \text{zero-divisor} && \\ [ 7]_{12} &= \{ \dots, && -17, && -5, && 7, && 19, && 31, && \dots \} && \text{invertible} && \\ [ 8]_{12} &= \{ \dots, && -16, && -4, && 8, && 20, && 32, && \dots \} && \text{zero-divisor} && \\ [ 9]_{12} &= \{ \dots, && -15, && -3, && 9, && 21, && 33, && \dots \} && \text{zero-divisor} && \\ [10]_{12} &= \{ \dots, && -14, && -2, && 10, && 22, && 34, && \dots \} && \text{zero-divisor} && \\ [11]_{12} &= \{ \dots, && -13, && -1, && 11, && 23, && 35, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
\(\mathbb{Z}_{13}\)#
\( \begin{aligned} n &= 13 \\ \mathbb{Z}_{13} &= \{ [0]_{13}, [1]_{13}, [2]_{13}, [3]_{13}, [4]_{13}, [5]_{13}, [6]_{13}, [7]_{13}, [8]_{13}, [9]_{13}, [10]_{13}, [11]_{13}, [12]_{13} \} \\ \end{aligned} \)
\( \begin{aligned} [ 0]_{13} &= \{ \dots, && -26, && -13, && 0, && 13, && 26, && \dots \} \\ [ 1]_{13} &= \{ \dots, && -25, && -12, && 1, && 14, && 27, && \dots \} && \text{invertible} && \text{self-inverse} \\ [ 2]_{13} &= \{ \dots, && -24, && -11, && 2, && 15, && 28, && \dots \} && \text{invertible} && \\ [ 3]_{13} &= \{ \dots, && -23, && -10, && 3, && 16, && 29, && \dots \} && \text{invertible} && \\ [ 4]_{13} &= \{ \dots, && -22, && -9, && 4, && 17, && 30, && \dots \} && \text{invertible} && \\ [ 5]_{13} &= \{ \dots, && -21, && -8, && 5, && 18, && 31, && \dots \} && \text{invertible} && \\ [ 6]_{13} &= \{ \dots, && -20, && -7, && 6, && 19, && 32, && \dots \} && \text{invertible} && \\ [ 7]_{13} &= \{ \dots, && -19, && -6, && 7, && 20, && 33, && \dots \} && \text{invertible} && \\ [ 8]_{13} &= \{ \dots, && -18, && -5, && 8, && 21, && 34, && \dots \} && \text{invertible} && \\ [ 9]_{13} &= \{ \dots, && -17, && -4, && 9, && 22, && 35, && \dots \} && \text{invertible} && \\ [10]_{13} &= \{ \dots, && -16, && -3, && 10, && 23, && 36, && \dots \} && \text{invertible} && \\ [11]_{13} &= \{ \dots, && -15, && -2, && 11, && 24, && 37, && \dots \} && \text{invertible} && \\ [12]_{13} &= \{ \dots, && -14, && -1, && 12, && 25, && 38, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
\(\mathbb{Z}_{14}\)#
\( \begin{aligned} n &= 14 \\ \mathbb{Z}_{14} &= \{ [0]_{14}, [1]_{14}, [2]_{14}, [3]_{14}, [4]_{14}, [5]_{14}, [6]_{14}, [7]_{14}, [8]_{14}, [9]_{14}, [10]_{14}, [11]_{14}, [12]_{14}, [13]_{14} \} \\ \end{aligned} \)
\( \begin{aligned} [ 0]_{14} &= \{ \dots, && -28, && -14, && 0, && 14, && 28, && \dots \} \\ [ 1]_{14} &= \{ \dots, && -27, && -13, && 1, && 15, && 29, && \dots \} && \text{invertible} && \text{self-inverse} \\ [ 2]_{14} &= \{ \dots, && -26, && -12, && 2, && 16, && 30, && \dots \} && \text{zero-divisor} && \\ [ 3]_{14} &= \{ \dots, && -25, && -11, && 3, && 17, && 31, && \dots \} && \text{invertible} && \\ [ 4]_{14} &= \{ \dots, && -24, && -10, && 4, && 18, && 32, && \dots \} && \text{zero-divisor} && \\ [ 5]_{14} &= \{ \dots, && -23, && -9, && 5, && 19, && 33, && \dots \} && \text{invertible} && \\ [ 6]_{14} &= \{ \dots, && -22, && -8, && 6, && 20, && 34, && \dots \} && \text{zero-divisor} && \\ [ 7]_{14} &= \{ \dots, && -21, && -7, && 7, && 21, && 35, && \dots \} && \text{zero-divisor} && \\ [ 8]_{14} &= \{ \dots, && -20, && -6, && 8, && 22, && 36, && \dots \} && \text{zero-divisor} && \\ [ 9]_{14} &= \{ \dots, && -19, && -5, && 9, && 23, && 37, && \dots \} && \text{invertible} && \\ [10]_{14} &= \{ \dots, && -18, && -4, && 10, && 24, && 38, && \dots \} && \text{zero-divisor} && \\ [11]_{14} &= \{ \dots, && -17, && -3, && 11, && 25, && 39, && \dots \} && \text{invertible} && \\ [12]_{14} &= \{ \dots, && -16, && -2, && 12, && 26, && 40, && \dots \} && \text{zero-divisor} && \\ [13]_{14} &= \{ \dots, && -15, && -1, && 13, && 27, && 41, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)
\(\mathbb{Z}_{20}\)#
\( \begin{aligned} n &= 20 \\ \mathbb{Z}_{20} &= \{ [0]_{20}, [1]_{20}, [2]_{20}, [3]_{20}, [4]_{20}, [5]_{20}, [6]_{20}, [7]_{20}, [8]_{20}, [9]_{20}, [10]_{20}, [11]_{20}, [12]_{20}, [13]_{20}, [14]_{20}, [15]_{20}, [16]_{20}, [17]_{20}, [18]_{20}, [19]_{20} \} \\ \mathbb{Z}_{20}^* &= \{ [1]_{20}, [3]_{20}, [7]_{20}, [9]_{20}, [11]_{20}, [13]_{20}, [17]_{20}, [19]_{20} \} \\ \end{aligned} \)
\( \begin{aligned} [ 0]_{20} &= \{ \dots, && -40, && -20, && 0, && 20, && 40, && \dots \} \\ [ 1]_{20} &= \{ \dots, && -39, && -19, && 1, && 21, && 41, && \dots \} && \text{invertible} && \text{self-inverse} \\ [ 2]_{20} &= \{ \dots, && -38, && -18, && 2, && 22, && 42, && \dots \} && \text{zero-divisor} && \\ [ 3]_{20} &= \{ \dots, && -37, && -17, && 3, && 23, && 43, && \dots \} && \text{invertible} && \\ [ 4]_{20} &= \{ \dots, && -36, && -16, && 4, && 24, && 44, && \dots \} && \text{zero-divisor} && \\ [ 5]_{20} &= \{ \dots, && -35, && -15, && 5, && 25, && 45, && \dots \} && \text{zero-divisor} && \\ [ 6]_{20} &= \{ \dots, && -34, && -14, && 6, && 26, && 46, && \dots \} && \text{zero-divisor} && \\ [ 7]_{20} &= \{ \dots, && -33, && -13, && 7, && 27, && 47, && \dots \} && \text{invertible} && \\ [ 8]_{20} &= \{ \dots, && -32, && -12, && 8, && 28, && 48, && \dots \} && \text{zero-divisor} && \\ [ 9]_{20} &= \{ \dots, && -31, && -11, && 9, && 29, && 49, && \dots \} && \text{invertible} && \\ [10]_{20} &= \{ \dots, && -30, && -10, && 10, && 30, && 50, && \dots \} && \text{zero-divisor} && \\ [11]_{20} &= \{ \dots, && -29, && -9, && 11, && 31, && 51, && \dots \} && \text{invertible} && \\ [12]_{20} &= \{ \dots, && -28, && -8, && 12, && 32, && 52, && \dots \} && \text{zero-divisor} && \\ [13]_{20} &= \{ \dots, && -27, && -7, && 13, && 33, && 53, && \dots \} && \text{invertible} && \\ [14]_{20} &= \{ \dots, && -26, && -6, && 14, && 34, && 54, && \dots \} && \text{zero-divisor} && \\ [15]_{20} &= \{ \dots, && -25, && -5, && 15, && 35, && 55, && \dots \} && \text{zero-divisor} && \\ [16]_{20} &= \{ \dots, && -24, && -4, && 16, && 36, && 56, && \dots \} && \text{zero-divisor} && \\ [17]_{20} &= \{ \dots, && -23, && -3, && 17, && 37, && 57, && \dots \} && \text{invertible} && \\ [18]_{20} &= \{ \dots, && -22, && -2, && 18, && 38, && 58, && \dots \} && \text{zero-divisor} && \\ [19]_{20} &= \{ \dots, && -21, && -1, && 19, && 39, && 59, && \dots \} && \text{invertible} && \text{self-inverse} \\ \end{aligned} \)