This version is suitable for viewing within Frrraction or on any browser.

It is not synchronized with the Frrraction app. 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

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

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.

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 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

TRACE: For each cluster C

SHADOW: The

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] ∈ C_{u}

[a]⋅inv[a] = [ω_{u}]

[a]⋅[c]= [a]⋅[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 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].

SO UNITS ARE ALL ASSUMED TO BE COPRIME WITH m.

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:

Residues are
not an "ordered" collection so, as a residue, [u] is not "greater than" or
"less than" any other residue-divisor of m, whether they are common divisors
with m or otherwise! In fact, [m] = [0], so all nonzero mod-m-residues divide
[m]. So, the notion gcd(u,m) must not be confused with the nonsensical
gcd([u],[m]. This is one of the reasons we are still using the notation z
for real integers and [z] for residues.

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)=[_{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.

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.

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.

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.

a Michigan company since 1978

Most recent update of this guide: June 30, 2022, 12:30pmET

Copyright © GRS Enterprises, NLC, 2010-2022

Not void, even where prohibited. Your mileage may vary.