Prime Fields and Modular Arithmetic

Integers Viewed Modulo a Number

Modular arithmetic keeps track of remainders rather than the full size of an integer. For example, clock arithmetic identifies numbers that differ by a whole number of hours: on a seven-hour clock, \(2\) and \(9\) represent the same position. This idea also gives a small arithmetic system with finitely many elements. When the modulus is prime, that system has all the arithmetic properties of a field, including division by every nonzero element. That fact is useful later when linear algebra is carried out over finite fields.

Let \(m\ge 2\) be an integer. Two integers \(a\) and \(b\) are congruent modulo \(m\) if \(m\) divides their difference. We write \(a\equiv b\pmod m\). The residue class of \(a\) modulo \(m\), written \([a]_m\), is the collection of all integers congruent to \(a\) modulo \(m\). Each such class has exactly one representative among \(0,1,\ldots,m-1\), called its standard representative.

For instance, modulo \(7\), the integers \(2,9,-5\) all belong to the same class, because their differences are multiples of \(7\). We can use \(2\) as the standard representative of that class. The notation \([a]_m\) emphasizes that the integer \(a\) is being treated as a residue class, not as a particular representative.

These formulas use representatives, so we must check that choosing different representatives cannot change the answer. If \(a\equiv a'\pmod m\) and \(b\equiv b'\pmod m\), then \(m\mid(a-a')\) and \(m\mid(b-b')\). It follows that \(m\mid((a+b)-(a'+b'))\), so the sums represent the same class. For products,

and both terms on the right are divisible by \(m\). Thus the products also represent the same class. The operations are therefore well-defined: they do not depend on which representatives we choose. Their associativity, commutativity, and distributivity follow from the corresponding integer identities together with this well-definedness.

Computing in a Prime Field

To add or multiply residues, perform the usual integer operation and reduce the result to its standard representative. An additive inverse of \([a]_m\) is a class that adds to \([0]_m\); \([-a]_m\) always works. A multiplicative inverse of \([a]_m\) is a class \([c]_m\) such that \([a]_m[c]_m=[1]_m\). Multiplicative inverses are different: they do not exist for every nonzero residue when the modulus is composite.

The notation \([a]_p^{-1}\) is used only when \([a]_p\ne[0]_p\) and the inverse exists. The field property proved below guarantees that it exists for every nonzero class when \(p\) is prime. It is also unique: if \([a]_p[x]_p=[1]_p\) and \([a]_p[y]_p=[1]_p\), then

So there cannot be two different multiplicative inverses of the same nonzero class.

Why Prime Moduli Give Fields

A field is a set with addition and multiplication in which addition and multiplication are associative and commutative, multiplication distributes over addition, and there are distinct additive and multiplicative identities \(0\) and \(1\). Every element has an additive inverse, and every element other than \(0\) has a multiplicative inverse. The operations in \(\mathbb{F}_p\) already satisfy the identities inherited from the integers. The point that needs proof is the existence of a multiplicative inverse for every nonzero residue.

Proof. First suppose \(m=p\) is prime. The classes \([0]_p\) and \([1]_p\) are distinct because \(p\ge2\). Integer identities and well-definedness give the required associativity, commutativity, and distributivity. The class \([0]_p\) is the additive identity, \([1]_p\) is the multiplicative identity, and \([-a]_p\) is an additive inverse for \([a]_p\).

Now let \([a]_p\ne[0]_p\), and choose its standard representative \(a\) with \(1\le a\le p-1\). Consider the function that sends each nonzero residue \([x]_p\) to \([a]_p[x]_p\). Its output is nonzero: if \(ax\equiv0\pmod p\), then the prime \(p\) divides \(ax\). Since \(p\) does not divide \(a\), the prime divisor property implies \(p\mid x\), so \([x]_p=[0]_p\), contrary to the choice of a nonzero input.

This function is one-to-one. Indeed, if \([a]_p[x]_p=[a]_p[y]_p\), then \(p\mid a(x-y)\). Again \(p\nmid a\), so \(p\mid(x-y)\), which means \([x]_p=[y]_p\). There are \(p-1\) nonzero residues. A one-to-one function from this finite set to itself must take every value in the set: its \(p-1\) distinct outputs exhaust the \(p-1\) possible outputs. In particular, some nonzero \([x]_p\) satisfies \([a]_p[x]_p=[1]_p\). Thus every nonzero class has a multiplicative inverse, and \(\mathbb{F}_p\) is a field.

Conversely, suppose \(m\ge2\) is not prime. Then \(m=rs\) for integers \(r,s\) with \(1<r<m\) and \(1<s<m\). The classes \([r]_m\) and \([s]_m\) are nonzero, since neither \(r\) nor \(s\) is divisible by \(m\), but

If the residue classes modulo \(m\) formed a field, \([r]_m\) would have an inverse. Multiplying \([r]_m[s]_m=[0]_m\) by that inverse would give \([s]_m=[0]_m\), contradicting that \([s]_m\) is nonzero. Therefore the classes modulo a composite \(m\) do not form a field. The two directions prove the claim. \(\square\)

What Fails for a Composite Modulus

Common mistake: treating division like ordinary integer division. A tempting but wrong calculation is to say that \([3]_7/[2]_7=[1]_7\), perhaps because \(3/2\) is being informally rounded or simplified. Division in modular arithmetic means multiplication by the denominator's inverse. Since \(2\cdot4=8\equiv1\pmod7\), the inverse of \([2]_7\) is \([4]_7\), and the correct calculation is

Checking by multiplication confirms the correction: \([5]_7[2]_7=[10]_7=[3]_7\). Division by a residue is defined only when that residue has a multiplicative inverse; in a prime field, this means precisely that the denominator is nonzero.

Using the Arithmetic Reliably

For hand calculations, reduce after an operation or at the end; both approaches give the same residue class. Reducing along the way can keep numbers small. For an inverse, either test products with the nonzero standard representatives or use the Euclidean algorithm to express \(1\) as an integer combination of the number and the modulus. A product check is essential: a proposed inverse must give remainder \(1\), not \(0\).

The distinction between prime and composite moduli is not merely about which numbers happen to be convenient. With a prime modulus, every nonzero class can be used as a divisor, so the arithmetic satisfies the field requirements. With a composite modulus, the factorization of the modulus supplies nonzero classes whose product is zero, and at least one of those classes cannot have an inverse. This is why the notation \(\mathbb{F}_p\) is reserved for prime \(p\).