Mod m: A technical foundation

Introduction

If m > 1 is a specific euclidean integer^§ and z is any euclidean integer then [z] designates a residue modulo m, defined to be the entire collection of integers that appear in the arithmetic progression: ..., z-2m, z-m, z, z+m,z+2m, ... In modulo 3 for example, [z]={...,z-6, z-3, z, z+3, z+6,...}. That infinite collection of integers IS the residue [z]. Each integer y in that progression is a member of [z], and [y] is synonym for [z].

The collection of all those collections (the arithmetic progressions modulo m) is called the residue system modulo m, denoted by Z_m. The number of residues in Z_m is m.

Any integer in [z] can be used in place of z as a tag or label for referencing [z]. There is, however, a unique member of [z] in the real integer range from 0 to m − 1. We call that integer the remTag of [z]. The remTag can be calculated by a standard computer function (often called mod) which efficiently computes the remainder left over after dividing integer z by integer m. For example, 3 is the remTag of [19] modulo 8 because 19/8 leaves remainder 3. We use [3] as the preferred synonym for [19] and, generally [the remTag of [z]] as the preferred synonym for [z].

To say that residues [z₁] and [z₂] are equal and write [z₁] = [z₂]  is just to say that the integers z₁ and z₂ are in the same residue class of Z_m i.e. the integer statement z₁ = z₂ + k⋅m is true for some integer k. In the more casual terminology introduced by Gauss, z₁ ≡ z₂ (mod m) means the same as saying [z₁]=[z₂], i.e. the residue [z₁] contains the same real integers as residue [z₂].

In the long term, this square-bracket notation gets tiresome—"notational bureaucracy" they once called it in the Berkeley Math Circle—but in the present context we need it to be very clear to the reader exactly which symbols denote residues and which denote integers. Eventually Frrraction's documentation will revert to Gauss's, generally using the remTag as the integer label, and depending upon context to make it clear which are residues and which are integers.

Now consider four euclidean integers a, b, c, d and positive euclidean integer m > 1 such that a ≡ b (mod m) and c ≡ d (mod m).

In modular arithmetic the following identities then hold with integers a, b, c, d re-cast as residues. Just for this discussion, and almost nowhere else, we'll refer to residues modulo m using the notation [z] where z is an integer. So, [a], [b], [c], and [d] are the present topic.

always exists such that: [a]+neg[a] = [a]-[a] = 0.

SUBTRACTION: [a]-[c] = [a] + neg[c]. [a]-[c] = [b]-[d].

MULTIPLICATION: [a]⋅[c] = [b]⋅[d].

DIVISION: [a]/[c] = [b]/[d], but there's much more to say about division, starting with:
CLUSTER: The residue system Z_m (for any particular real integer m > 1) partitions naturally into subcollections called clusters. For each residue [f] whose remTag f divides m there is a unique cluster C_f that contains [f] as a member; [f] is called the center of that cluster. Each residue [r] (modulo m) is a member of C_f for the unique divisor f=gcd(r,m) of m. We extend the notation to say that C_r is the cluster of any residue r and to make C_r be a synonym for C_f for any member r of C_f. This simplifies some discussions when we know a member of a cluster but not its focus. We note in passing that C₁, the cluster whose center is 1, is the set consisting of all the Euler units modulo m. Similarly (?) cluster C₀ consists of the single residue 0.
TRACE: For each cluster C_f there is a collection T_f called the trace of the cluster. If r is in C_f then T_r is a synonym for T_f.
SHADOW: The shadow of C_f is the collection of all members of the trace that are not members of the cluster.

RECIPROCAL: There are two kinds of residues: units and integers^§. The main distinction is that the cluster of each unit is a group but the cluster of an integer is not a group.

If [u] is a unit then there exists in its cluster a unique identity element ome[u] a.k.a. [ω_u] such that

weakDIVISION: Setting aside a,b,c,d and recasting in the more-familiar terms of numerator n, denominator d, and quotient q should make this easier to follow, so: [n]/[d] denotes residue [q] (a quotient) and [r] (the remainder) which together satisfy the equation [n] = [d]⋅[q] + [r] where [r] is a residue mod μ=m/g where g=gcd(d,m), and q is a residue mod m. The value of [r] is always well defined, and solution for [q] always has g interchangeable alternative values (so, without extra qualifiers, "the" quotient defined this way is not unique unless d is an Euler unit). If [r] = 0 we say [d] divides [n] and write [d]|[n]. This weak definition of residue quotient [q] is quite similar to the definition for integers but a broader range of divisors is available, the residue remainder [r] is quite different, and uniqueness of the quotient demands further attention.

EXPONENTIATION: [a]^e = [b]^e where integer e is positive. If m is prime then [a]^(m-2) equals [1]/[a], and [a]⋅([1]/[a]) ≡ [a]/[a] ≡ [1]. Ever since Euler, that has been a popular way to divide by [a] and to compute inv([a])—but it's only guaranteed to work if m is prime or in the special cases where a and m are relatively prime^§.

FOCUS #1 ON DIVISION: This is the most obscure of the arithmetic ops, but this division is partly similar to integers and partly similar to real numbers.

The existence theorem, i.e. the condition for existence of quotient [n]/[d] (mod m), is: [d] divides [n] if and only if g.|.n, i.e. integer g divides the remTag of n, where g=gcd(d,m). Another way to say it is, [d] divides [n] if and only if g can be cancelled from n⋅/⋅d to produce ν⋅/⋅δ; this makes the reduced denominator δ be relatively prime to reduced modulus μ = m⋅/⋅g; thus [ν]/[δ] can be calculated as [q]=[ν]⋅inv([δ]) with [r]=[0].

Residues share the following definition with integers: A "unit" is any number that divides 1. Another way to say it is: A unit u is any number that has a reciprocal, denoted either u^-1 or inv(u).

Just like integers, among residues none but units divide units. Among real integers, the only units are 1 and -1. Among residues (mod m), the corresponding units are [1] and [m−1]. But here's a big difference between integers and residues: There are commonly many residue-units, not just [1] and [m−1]: A unit [u] (mod m) is any residue [u] for which u is relatively prime to m, i.e. gcd(u,m)=1. (Notice: I don't try to speak of [u] being relatively prime to anything.) For example, there are 24 units mod 45: [1], [2], [4], [7], [8], [11], [13], [14], [16], [17], [19], [22], [23], [26],[28], [29], [31], [32], [34], [37], [38], [41], [43], and [44]. Over HALF of all mod-45 residues are units!

There's a potential ISSUE here:

Just like integer units, residue units divide anything. Each of the mod-45 units, for example, divides all of the mod-45 residues; picking on the mod-45 residue-unit [17] for example: 0/17=0 1/17=8 2/17=16 3/17=24 4/17=32 5/17=40 ... 43/17=29 and 44/17=37. All the units always divide all the numbers, be they integers or residues.

We consider the possibility of prime residues, by letting residues share the following integer definition:

Residue n is said to be a "modular prime" if it has only trivial divisors: itself, itself times units, and units. (Those divisors are "trivial" in the sense that every nonzero residue is so divisible.)

Modular Primes example, modulo 45: [9] is of course divisible all the trivial divisors (itself, any unit, and itself times any unit) but also by the non-unit [6]--so [9] is not prime mod 45. Likewise [10], along with its trivial divisors, has the non-unit 5 as a divisor, so [10] is not prime. On the other hand, [3] is divisible only by the trivial divisors, so [3] is a mod-45-prime (the ONLY mod-45 prime, in fact).

A given modulus m admits some modular primes only if m is itself not a prime integer. No modular prime is a unit--otherwise, it would divide all residues, even any other primes--and primes dividing other primes would be peculiar indeed. As far as I know so far, all modular primes are residues whose proper name is a prime factor of m, but the converse--all prime factors of m are primes modulo m--is surely false.

What goes WRONG when the MODULUS m itself is NOT PRIME? Everything gets more Byzantine, that's what! And maybe more interesting? Before Galois, the progression of advancing number-like-things was: ""counting-numbers", "zero", integers, "rational numbers", "irrational numbers","transcendental numbers", and "real numbers". Ever since Galois, the progression of more-and-more-number-like things has been: "groups", "rings", "integer domains", "fields",... Technically, when m is prime the residues mod m constitute a "field", which means they behave much like rational numbers. That's a big deal, it means that arithmetic works pretty much like you would expect. For example, the formula for the sum of the first n integers is n*(n+1)/2; it holds for the residues modulo any prime m, too, e.g. 1+2+3+4+5 (mod 11) and 5*6/2 (mod 11) are equal, just as 1+2+3+4+5 (integer) and 5*6/2 (integer) are equal.

When the modulus is composite, however, many such rational-expectations fail. Addition, subtraction, multiplication, and integer powers still work OK, but division gets trickier. Fermat's Little Theorem, for instance, does not apply when m is composite and in fact [e]^m is not always [e] (e.g. m=12, [e]=10); moreover, [e]^(m-1) is not always 1 even if [e]^m does happen to be [e] (e.g. m=12, [e]=9)--even though, as I just said, integer powers still work: [e]^m still equals [e]*([e]^(m-1). So, if for some k it happens that [e]^k=[e] and [e]^(k-1)=[₁], you can rest assured that [e]^(k-2) does necesarily equal the reciprocal of [e] (e.g. m=12, [e]=7, k=11). Composite moduli are tricky.

Another thing that fails is The Fundamental Theorem Of Arithmetic: unique factorization is out the window! [a]*[b]=[a]*[c] does not guarantee that b=c. Example: [10]*[10]=[10]*[19] mod 45, but [10]≠[19]. You can't always cancel even if the common factor is the mod-45-prime [a]=[3], e.g. [3]*[18]=[3]*[33]. Seems worse when you think of it this way: [3]*[x]=[3]*[18] does not let you conclude [x]=[18]. Non-prime modulus calls for great attention to detail!

Yet another difference when the modulus is composite: Fermat's approach of using powers of [e] to find inv([e]) does not work unless m is prime. A variant due to Euler still does, but you need to know his "totient function Phi(m)", which requires first finding all the prime factors of m and then doing some more arithmetic. Frrraction's M|P|R-Residue mode uses a much simpler continued fraction to do it.

Residues with composite modulus are not chaotic, however: Working with units (residues [e] for which gcd(m,e)=1) is almost as good as m being prime. In fact, the most special thing about m being prime is that ALL its nonzero residues are units.

EULER’S TOTIENT FUNCTION What’s with?

Our hero Leonhard Euler (he should be anyone's hero who likes numbers--call him Lennie) was the first to publish a proof of Fermat’s Little Theorem, which states that if m is prime and r is a residue mod m, then r^m==1 (mod m) or, equivalently, r^(m-1)==1 (mod m).

Unfortunately, the converse is NOT true. The (invalid) converse is: If r^(m-1)==1 mod m holds for some m and r then m is prime. Otherwise The Little Theorem would provide an easy test for whether m is prime. Worse, you cannot conclude that m is prime even if the Little Theorem holds for ALL r co-prime to m. The m-examples of that worst failure are called "Carmichael Numbers", or “false primes" (Carmichael Numbers are not the same as Carmichael's Lambda function). (Of course, if you find a value for r that violates the Little Theorem itself, that DOES tell you that m is NOT prime. But, since most numbers are not prime, that news is not very exciting.) Some more-elaborate prime-tests that make really high-reliability prime/composite choices have been constructed around the Fermat idea. But, enough of prime testing for now--Frrraction has a built-in function for that, for m up to a few billion.

Euler liked Fermat's result but didn’t like that it required m to be prime. He came up with what came to be called Euler’s Totient Function Phi(m) and proved (in the Euler-Fermat Theorem) a property similar to Fermat's: r^Phi(m)==1 for any integers r and m that are co-prime, i.e. gcd(r,m)==1 (mod m). This reduces to the Little Theorem if m is prime, since ruler’s Phi in that case is m-1.

Carmichael proved a stronger result, replacing Euler's Phi by a Lambda function: Under the same conditions as the Euler-Fermat Theorem, Lambda(m) is the SMALLEST number for which e^Lambda(m)==1 is true of all residues r coprime to m. [Try to think through that three times fast in a row:-] Lambda(m) always divides Phi(m) and is often smaller than Phi(m).

Unfortunately, Phi(m) is not easy to compute. One way is to search all the numbers r from 1 to m-1, evaluating gcd(r,m) for each, and counting those for which the gcd is 1. Another way is to find all the distinct prime factors f1,f2,…,fn of m; then Phi(m) = m times (1-1/f1) times (1-1/f2) times … times (1-1/fn). You can write a Frrraction-applet for that, which uses the CFunction “isPrime” and works well for m-values up to pMax.

Frrraction's M|P|R-Residue mode uses a simpler method for computing modular reciprocals, Resh's SCF (Shortened Continued Fraction) method (see the Frrraction Guide 104, Intro to Modular Arithmetic, The SCF Inversion Method, mRemainders as Special Numbers, page 12).

And now Frrraction has two instructions called EulerPhi: a CF-version and an hp-version, providing two different interfaces to Phi and Lambda.

Modular Myopia

We'll now drop the awkward convention of putting []-brackets around residues, and count on you to stay alert to the context to distinguish between integers and residues. Part of the context will be Gauss's congruence notation a == b (mod m) for residues, and ordinary equals a = b for integers. (Actually, Gauss used the three-line-equality-sign ≡ instead of ==, but == is much easier to type and recognize.) Also, any reference to order, such as a < b, will point to a and b being integers. The 'G' of 'GCD(a,b)' is another order-reference: 'Greatest' meaning largest.

Any positive integer m serves as modulus for exactly one unique collection of residues: the residues modulo m. All integers are residues for any modulus, and modular math is the same as integer math--with only one single little change: If the difference p - q between two integers p and q equals the modulus or any multiple of the modulus, then modular math sees p and q as being essentially the same residue--Gauss said, "p and q are congruent". This "modular near-sightedness" is the defining property of modular math.

Modular myopia reminds us of the similar near-sightedness that gives school children lots of trouble when they first encounter fractions after spending several years learning integers: If p q and r are three nonzero integers then fraction math says p/q = (p*r)/(q*r). That is to say, it sees no difference between p over q on the one hand, and p times r over q times r on the other. We all learned to blithely say, "The r cancels."

At root, it's the whole reason modular math is not the same as integer arithmetic. Really.

It follows from the myopia that the residues for one modulus are not the same creatures as the residues for any other modulus; for example, [18] is a residue modulo 18 and also for modulus 19, but 18==0 mod 18 while 18==-1 mod 19 and 0==-1 is false for both moduli. There is only one collection of integers, but there are infinitely many collections of residues. (You'll never learn infinitely many addition and multiplication tables by heart! That's a good thing, because it means you don't need to try. And besides, except for adjusting to the myopia, they are the same as the integer tables.)

Another good thing about the myopia: For any particular positive integer m we only need to know m names for the residues modulo m; the standard names are: 0 1 ... and m-1.

Example: For m=5 the standard names are 0 1 2 3 and 4. The next integer up, 5, differs from integer 0 by m so 5 and 0 are not different residues modulo 5. Likewise, modular -1 is the same as 4 (modulo 5). And -6 is the same as -1, and... OK, you're on it.

More to come... in later Frrraction updates. In the meantime, tap M|P|R to get to Frrraction's Modular Residue view.

FOCUS #2 ON DIVISION:

Modular division is about solving the equation n == q*d + r (mod m) for quotient q and remainder r, given dividend n and divisor d modulo m. Solving the equation comes down to re-casting it to something we know how to do: finding the reciprocal of a unit. Units always have reciprocals, so that approach always works. We'll consider three progressively deeper cases.

Case 1: If the divisor d and modulus m are mutually prime, i.e. gcd(m,d)=1, then d has a unique reciprocal inv(d) and the quotient q is always given by n*inv(d) with remainder r==0. Example Case 1: Find q and r for 18/23 mod 30. The reciprocal of 23 exists because gcd(30,23)=1; it is inv(23)==17. Thus, r==0 and q==n/d==n*inv(d)==18*17==6 (mod 30). If modulus m is prime then Case 1 always applies, all nonzero residues are units and therefore have reciprocals. If modulus m is composite then some possible divisors share factors with the modulus; those divisors do not have reciprocals, and the division equation with r==0 may or may not have solutions. The second case sorts this out.

Case 2: If the divisor d is not prime relative to modulus m then, defining g=gcd(m,d), we have g > 0 instead of g = 0. It saves the day if g happens to divide the dividend n. In this case (which includes Case 1 as a special case since 1 certainly divides n) we can cancel g from n and d as a common factor, reducing the problem to solving n' == q' * d' (mod m') where gcd(m',d')=1, a Case-1 problem. Define n' = n/g, d' = d/g, and m' = m/g; note that g integer-divides all three of n, d, and m; moreover, gcd(m',d')=1 since g contains all the factors that m and d had in common. Thus d' has a reciprocal modulo m' and we can write q' == n'*inv(d') mod m'. From n' == q'*d' mod m' it follows that n'*g == q'*(d'*g) (mod (m'*g), i.e. n == q'*d (mod m), so q' provides the desired quotient, with remainder r == 0.

A new "buyer-beware" wrinkle arises in Case 2: We can add ∆ to q' and get another solution of the division equation, using ∆ = m' or any multiple of m'. "The" quotient is not unique. Depending on specific applications, this may or may not be of any significance. Myself, free of any specific applications, I like it.

Example Case 2: Find q and r for 18/21 mod 30. The divisor 21 has no reciprocal modulo 30 since g=gcd(30,21)=3 is a factor they share. Dividing n == q*d mod m through by g converts the equation to be solved into n'==q*d' (mod m'), where n'=n/g=6, d'=d/g=7, and m'=m/g=10. In this case g evenly integer-divides all three. Note that since m' and d' are prime to each other, we know that d' has a reciprocal inv(7)==3 mod m'; so q'==n'/d'== n'*inv(d')== 6*3==8 (mod 10); thus 18/21 == quotient 8 with remainder 0. Of course, adding the modulus m' produces congruent quotients; Frrraction renames m' as ∆ = 10 to yield equivalent quotients; it stops after adding ∆ because 8, 18, and 28 are distinct modulo 30 but 38, 48,... are not new. These results are easily checked by multiplying q=8, 18, 28,... by d'=7 to confirm that each yields n'=8 mod 10. Scaling back up n'-->n==18, d'-->d==21, and m'-->m=30 by integer-multiplying by g=3, we that those are the desired values for q, confirmed by multiply each by d==21 yields n=18.

Case 3A: Find q and r to solve 16/6==q with remainder r, i.e. n == q*d + r (mod m) with n==16, d==6, m==30. The calculations are: g=gcd(m,d)=6; r=4=remainder after integer-dividing n by q; m'=30/g=5=∆, n'=(n-r)/g=12/6=2, d'=d/g=1. So the reduced equation is n'==q'*d' mod m' or 2==q'*1 mod 5 whose solutions are q'=2, 7, 12,...,27, 32, 37,... Of these, only q=2, 7, 12,..., and 27 are distinct modulo 30. Case 3A was too easy, what with d'==1. Let's try...

Case 3B: Find q and r for 16/12 mod 30. This time the calculations are: g=gcd(m,d)=gcd(30,12)=6; r=4=remainder after integer-dividing n by g; m'=30/q=5=∆, n'=n/g=2, d'=d/g=2. So q'=n'/d'=2/2=1, so q=q'+∆=1,6,11,...,26 and no remainder. Confirm by noting that the modulo-30 product of d=12 times any of those q-values modulo 30 is always 12; adding the remainder r=4 thus always yields n=16. Check. Although Case 3B required a nonzero remainder, it was also too easy, what with d'==n' so n'/d' was simply 1. Let's try a more typical...

Case 3C: Find q and r for 16/9 mod 30. Solution: g=3, r=1, m'=10=∆, n'=5, d'=3, so q'=5*inv(3)==5*7==35==5,15,25,... (mod 10), so q==5,15,25 and r=1. Frrraction describes this as 16/9 = 5 ∆10 r1. Checking: 15*9+1==15+1==16 mod 30. Yup.

About Frrraction