Fields of Prime Order

A finite system of arithmetic may seem like a strange idea, but we do use them in everyday life. Hours on the clock commonly run from 1 to 12, and then 'wrap around" to resume at 1. The numbers are not just arbitrary labels; we do arithmetic with them. One might say: 5 hours after 9 o'clock is (pause) 2 o'clock. During the pause, one thought something like this: "9 + 5 = 14. But 14 - 12 = 2." In effect, 12, or a multiple of 12, was discarded. The standard way of saying this is 14 is congruent to 2 modulo 12, or

14 ≡ 2 (mod 12) .
Generally, a ≡ b (mod m) means that a – b is a multiple of m.

If we assume that two integers are the same whenever they are congruent modulo m, then we have the "integers modulo m." They can be represented by 0, 1, …, m–1. Besides adding and subtracting, we can multiply integers modulo m; for instance, 3 × 7 ≡ 9 (mod 12). Addition and multiplication behave pretty much as they do for ordinary integers; for instance a × b ≡ b × a (mod m). Multiplication is a little strange in one way: a product may be 0 even when neither factor is 0. For instance, 3 × 4 ≡ 0 (mod 12). If m is not prime, there will be such cases.

But if m is prime, then there are no cases where the product of two numbers is (congruent to) 0, unless one of the factors is. In fact, if p is prime, and a and b are integers not congruent to 0 (mod p), then the equation a × x ≡ b (mod p) always has a solution, which is unique (mod p). In the context of the integers modulo p, we might as well denote that value by b ÷ a.

To compute b ÷ a without sorcery, see the link "Division Modulo n" above.

So, the integers modulo a prime p have addition, subtraction, multiplication, and division defined, without leading out of that finite set. Mathematicians say that they form a "field." This one is the field of order p, that being the number of distinct elements in it. Among the common notations for this field is Fp. In talking about arithmetic inside Fp, I will drop the specification of "(mod p)" and use a plain equals sign instead of ≡.

A brief attack of pedantry

What shall we call the elements of Fp ? Some of the time, I think we can get away with calling them 0, 1, 2, etc. and trust to the context to show that we mean these numbers to be "(mod p)". But at other times we want to mention ordinary numbers and numbers "(mod p)" in the same breath. To make things less ambiguous, if x is an ordinary integer, we will use the notation μ(x) to mean "x modulo p" as an element of Fp . In extreme cases we may have to be specific about which value of p is meant, and then we will write μp(x).

To make the concept of Fp more familiar, I have provided a simple prime-field calculator. At the top is a menu from which you can select the prime, or "modulus". The calculator is organized like other calculators, to give the values of a + b, a - b, a × b, and (if b ≠ 0), a ÷ b.

Modulus
Cannot divide by zero

When you have chosen a modulus, the calculator will work much like any four-function calculator... except, of course, for giving different answers. If the modulus is 101, you can compute 12 times 12 by pressing "1", "2", "×", "1", "2", "=" ... and the answer is "43". Why? The "Show Why" button displays a proof that μ(12) × μ(12) = μ(43). It shows that 12 × 12 = 144, and a suitable multiple of the modulus can be subtracted from 144 to yield 43. With the same modulus, we find μ(12) ÷ μ(13) = μ(32), which may seem even stranger. Well, this is equivalent to saying that μ(32) × μ(13) = μ(12), which "Show Why" proves in the same way, multiplying 32 by 13 and subtracting a multiple of the modulus.

If a result has been displayed, or a proof of its validity, you can examine the effect on the given problem of changing the modulus.


Last modified on $Date: 2015-05-09 12:50:02 -0400 (Sat, 09 May 2015) $

Christopher J. Henrich