This version is suitable for viewing within Frrraction or on any browser.
It is not synchronized with the Frrraction app.This article was written quite early in the author's work, and much of it is out-dated.
The Introduction correctly presents the deep connection and distinction between
integers and residues, and is good to keep. Some corrections and clarifications have been
inserted here and there more recently, but the main reasons for inclusion are to remind me
of a few of my own early ideas, misunderstandings, and side-tracks — such as the naive hope
that there might be modular versions of the prime numbers which are so foundational for real
integers — which are of mostly historical interest for me.
Ignore occasional references
to the iPhone app named Frrraction; it is so attuned to my own personal style and my own numeric
interests that I long ago lost interest in supporting it on the App Store.
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 a synonym for [z].
The collection of all those collections (the collection of all those arithmetic progressions) is called the residue system modulo m, and denoted by Zm. It is also called "the ring Z/mZ". The number of residues in Zm is m.
Any integer in [z] can be used in place of z as a name 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 m-remainder of [z]. The m-remainder 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 m-remainder of [19] modulo 8 because 19/8 leaves remainder 3. We use [3] as the preferred synonym for [19] and, generally [the m-remainder of [z]] as the preferred synonym for [z].
To say that residues [z1] and [z2] are equal and write [z1] = [z2] is just to say that the integers z1 and z2 are in the same residue class of Zm i.e. the integer statement z1 = z2 + k⋅m is true for some integer k. In the more casual terminology introduced by Gauss, z1 ≡ z2 (mod m) means the same as saying [z1]=[z2], i.e. the residue [z1] contains the same real integers as residue [z2].
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 m-remainder 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 one 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.
ADDITION: [a]+[c] = [b]+[d]. A unique additive inverse-[a] = neg[a]
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 Zm (for any particular real integer m > 1) partitions naturally
into subcollections called clusters. For each residue [f] whose m-remainder f
divides m
there is a unique
cluster Cf that contains [f] as a member; [f] is called the center of that cluster.
Each residue [r] (modulo m) is a member of
Cf for the unique divisor f=gcd(r,m) of m. We extend the notation to say that
Cr is the cluster
of any residue r and to make Cr be a synonym
for Cf for any member r of Cf. This simplifies some discussions when
we know a member of a cluster but not its center. We note in passing that C1, the cluster
whose center is 1, is the set consisting of all the Euler units modulo m. Similarly (?) cluster
C0 consists of the single residue 0.
TRACE: For each cluster Cf there is a collection Tf called the trace of
the cluster. If r is in Cf then Tr is a synonym for Tf.
SHADOW: The shadow of Cf 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
[a]⋅[ωu] = [a] ∀ [a] ∈ Cu
[a]⋅inv[a] = [ωu]
There's a weak form of unique factorization which says that, if [a]≠[0], the equality
[a]⋅[c]= [a]⋅[d]
guarantees that [c] = [d].
That's always true of real numbers and real integers, and certainly true for residues if
[a] is an Euler unit.
It is also true if [a] is a residual unit and both residues [c] and [d] are members of the trace [Ta],
i.e. if [c] and [d] have the property that [ωa]⋅[c]=[c] and
[ωa]⋅[d]=[d].
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 m-remainder 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].
THE FOLLOWING WAS PRE-RESIDUAL UNITS AND INTSResidues 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!
§ When this was written, "unit" meant euler unit, and by modular divison I meant gaussian division.
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.
MODULAR PRIMES?We consider the possibility of prime residues, by letting residues share the following definition from integers:
§ When this was written, "unit" meant euler unit, and by modular divison I meant gaussian division.
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 in which case all residues are units§. 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.
§ Remember, at the time of original writing,
"units" meant just "gaussian
(euler) units" and modular division was only gaussian division. Updating the m=45
example to iu-division, we have that 5 and 9 are modal units and 3 is an int
(a modal integer). 3 does not divide 9. Moreover 3, 5, and 9 do not divide
each other. The members of the division-clusters C3, C5,
and C9 would all be "modal primes" by the present notion. But...
Is 18 really a trivial divisor of 9? Consider, 18 is congruent to 9⋅2 and 2 is an
euler unit, but 18 is also congruent to 9⋅36 and 36 is not an euler
unit! In fact, 36 is the identity element of the unit-group C9 so all six
members of C9
have that dual character of being trivial divisors of each other and
non-trivial divisors of each other. Should each of the six be considered to be
a separate prime? or not a prime at all, since each is divisible by a non-trivial
divisor?
The bright idea of modular primes has fizzled out.
Next consider: 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", "euclidean integers"", "rational numbers", "irrational numbers","transcendental numbers", and "real numbers". Ever since Galois, the progression of more-and-more-number-like things has been: "lagrangian 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 does so happen that [e]^k=[e] and [e]^(k-1)=[1], you can rest assured that [e]^(k-2) does also necessarily equal Gauss's 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! even limited versions fail: [a]⋅[b]=[a]⋅[c] with a ≠ 0 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] — [x] could just as well be [3] or [33]. Non-prime modulae call for great attention to detail!
§ We no longer believe in the idea of modular primes, but the example with 3 as a modular integer is bad enough.
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.
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 a few billion.
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.
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 algebraic ring: 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.
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 > 1 instead of g = 1. It makes Case 2 if that common factor 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 obviously not unique. Depending on specific applications, this may or may not be of any significance. Myself, free of any specific applications, I prefer quotients to be unique, not ambiguous.§
§ One of our discoveries (much more recent than this ResidueTech.html file) is a modular iu-division algorithm — and one of its main claims to value is the uniqueness of all its quotients.
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 q; 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 see that those are the desired values for q; confirm by multiplying each by d==21, yielding n=18 for each q.
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.