Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Modular Arithmetic

Field: Elementary Number Theory

The study of modular arithmetic.

Sequence of Expressions

Let n∈Z+n \in \mathbb{Z}^+. The set of integers modulo nn, denoted Z/nZ\mathbb{Z}/n\mathbb{Z}, forms a commutative ring under the operations of addition and multiplication, defined by the congruence relations. Specifically, for any a,b,c∈Za, b, c \in \mathbb{Z}, the operations are: \begin{enumerate} \item Addition: [a] + [b] = [a+b] \item Multiplication: [a] \cdot [b] = [a \cdot b] \end{enumerate} The basic properties are derived from the ring axioms and are summarized as follows: \begin{itemize} \item Commutativity: [a]+[b]=[b]+[a][a] + [b] = [b] + [a] and [a]⋅[b]=[b]⋅[a][a] \cdot [b] = [b] \cdot [a] \item Associativity: ([a]+[b])+[c]=[a]+([b]+[c])([a] + [b]) + [c] = [a] + ([b] + [c]) and ([a]⋅[b])⋅[c]=[a]⋅([b]⋅[c])([a] \cdot [b]) \cdot [c] = [a] \cdot ([b] \cdot [c]) \item Distributivity: [a]⋅([b]+[c])=([a]⋅[b])+([a]⋅[c])[a] \cdot ([b] + [c]) = ([a] \cdot [b]) + ([a] \cdot [c]) \item Exponentiation: For [a]∈Z/nZ[a] \in \mathbb{Z}/n\mathbb{Z}, [a]k=[a]⋅[a]⋯[a] (k times)[a]^k = [a] \cdot [a] \cdots [a] \text{ (k times)}. Furthermore, the multiplicative group of units is (Z/nZ)∗={[a]∈Z/nZ∣gcd⁡(a,n)=1}(\mathbb{Z}/n\mathbb{Z})^* = \{[a] \in \mathbb{Z}/n\mathbb{Z} \mid \gcd(a, n) = 1\}, which is a group under multiplication.
Let nn be a positive integer. The multiplicative group of units modulo nn, denoted by (Z/nZ)∗(\mathbb{Z}/n\mathbb{Z})^*, is a finite abelian group whose order is ϕ(n)\phi(n). The exponent of this group, λ(n)\lambda(n), is the smallest positive integer such that aλ(n)≡1(modn)a^{\lambda(n)} \equiv 1 \pmod{n} for all a∈(Z/nZ)∗a \in (\mathbb{Z}/n\mathbb{Z})^*. Furthermore, the structure theorem for finite abelian groups dictates that (Z/nZ)∗(\mathbb{Z}/n\mathbb{Z})^* is isomorphic to the direct product of cyclic groups whose orders are determined by the prime factorization of nn. Specifically, if n=p1k1p2k2⋯prkrn = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}, then (Z/nZ)∗≅∏i=1r(Z/pikiZ)∗(\mathbb{Z}/n\mathbb{Z})^* \cong \prod_{i=1}^{r} (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^*. The exponent λ(n)\lambda(n) is given by the least common multiple of the exponents of the component groups: λ(n)=lcm⁡(λ(p1k1),…,λ(prkr))\lambda(n) = \operatorname{lcm}(\lambda(p_1^{k_1}), \dots, \lambda(p_r^{k_r})). For prime powers pkp^k, the exponent λ(pk)\lambda(p^k) is defined as:\n\begin{itemize}\item If p=2p=2 and k≠1k \ne 1, λ(2k)=2k−2\lambda(2^k) = 2^{k-2}.\item If pp is an odd prime, λ(pk)=ϕ(pk)=pk−1(p−1)\lambda(p^k) = \phi(p^k) = p^{k-1}(p-1).\end{itemize}
Intermediate
If pp is a prime number, then for any integer aa, the number ap−aa^p - a is an integer multiple of pp.\nap≡a(modp)a^p \equiv a \pmod{p}