to the Main Frrraction Guide→

Mod m Introduction

This website is supported by the iPhone app called Frrraction.

Current with Frrraction Version 0.96.11

Menu of Mod m Introduction

What residues are

Modular numbers, or residues, are a generalization of circular measurements such as hourly time: 1 through 24 o'clock on an analog clock (residues modulo 24); or compass heading: 1 through 360 degrees on a circle (residues modulo 360).

Modular arithmetic is about position and distance around such circles, adjusted to ignore full trips around the circle in either direction, as in: "What time is 17 hours later than 10 o'clock?"," or "4 hours earlier than 3 o'clock ?" The answers can be calculated by ordinary arithmetic as 10 + 17 = 27 and 3 - 4 = -1 — and then adjusted for the circle to get the normal residue answers: 27 - 24 = 3 (wee hours) and -1 + 24 = 23 o'clock (late evening) .

Frrraction treats only the most interesting version of modular arithmetic, the exact integer version.

The Modular Circle

Real numbers are well represented by positions and distances along an infinitely long straight line, the real line. Modular numbers are similarly represented by positions and distances around a circle, the modular circle.

The modular circle brings a wrinkle to the position metaphor: Each position around the modular circle, from zero to just shy of the modulus m, represents a unique residue modulo m. But whereas each position on the real line has a unique label, each position on the modular circle logically admits infinitely many labels. The labels are integers, subject to integer arithmetic, while the positions they label are residues, subject to modular arithmetic. Adding integer multiples of the integer m to any label yields an alias for that label—another equivalent label for the identical residue position.

Names of residues

For each residue modulo m there is, among its infinitely many equivalent labels, a single label r that falls in the range 0 ≤ r < m. That unique label is called the residue, the residue's remainder, or the least residue.

It is customary but not mandatory to refer to residues by their remainders. For instance it would not be wrong to say that the sum 16 + 11 modulo 24 is 27, but commonly — as is standard usage in common examples like time and compass heading — we prefer to use the remainder, 3 — even though that requires a bit of extra computation.

Virtually every computer language makes that easy by providing a special and very efficient instruction — often called something like mod(r,m) — which replaces r by its modulo-m remainder. Frrraction uses such a function at the end of virtually all its modular computations, to support the "remainder" convention.

Negative residues

Negative positions on the number line are shown to the left of the 0-position. In contrast, a negative label on the modular circle, say t−m where t < m, requires no new space on the circle—it is simply an alias for the label t.

Modular arithmetic

The arithmetic of addition and subtraction plays well with such positional metaphors as displacements, on the modular circle as well as on the real number line: To add a positive number to a position is to move the added distance to reach a position—to the right on the line or clockwise on the circle; subtraction moves linearly left or circularly counterclockwise.

Modular multiplication, too, is mostly straightforward, but needs extra interpretation. Division has always been and remains the trickiest math op.

The math ops + and −

When 'op' is '+' or '−' then one but not both of the operands of the infix expression "a op b" can be a position, the other one or both must be a distance (displacement). If one operand is a position the result will be a position; it doesn't matter which of the two operands a or b is the distance. If both operands are distances, the result will be a distance.

The math ops • (same as × ) and ÷ (same as / )

Multiplication and division require careful interpretation, especially in the modular case. They operate on and produce only scalars and distances, not positions.

What could 3 o'clock times 10 o'clock or "three 10 o'clocks" mean? Nothing, certainly not along the lines of "30 square o'clocks". But, treating 3 as a scalar operating on 10 and 30 as distances, the arithmetic 3⋅10=30 hours later has clear meaning "on the clock"—and is the same "on the clock" as 6 hours later, and the same as 18 hours earlier, etc. This makes perfect sense of the formula for modular multiplication: multiply two residues by performing integer multiplication on their remainders, then adjust via multiples of the modulus to get the remainder of the result.

So. Multiplying or dividing a scalar by a scalar yields a scalar. Multiplying or dividing a distance by a scalar yields a distance. Dividing a distance by a distance yields a scalar.

Operationally, you don't need to be thinking about the scalar/distance/position distinctions all the time—they really are all just residues.

Division — history

Division always has been more devious than multiplication.

The original idea of division was to share some given quantity in equal portions among several recipients. The numerator n was a measure of the given quantity; the denominator d specified the intended number of recipients; and the quotient q was a measure of each of the resulting equal portions. The language suggests that d is a counting number — an answer to the question "How many?" — but usage evolved as arithmetic grew more abstract.

Real numbers use distances along the real line to model all three aspects: The measure of the given quantity, the count of the desired number of portions, and the measure of each resulting portion. Modular numbers do the same with distances around the modular circle.

Generically, denominator d is said to divide numerator n, and we write d | n, if there exists a solution of the equation d⋅q = n. If a solution for q exists and is unique, the solution is called the quotient and we write q = n/d.

The existence of quotients is more easily resolved for residues than for the euclidean integers, which actually stumble over it: All integers except 1 and −1 (the units) suffer a severe restriction on which real integers they can divide. One answer to the general question of which integers a given integer can divide is easily stated: d | n if and only if n is in the trace of d. (The trace of any number is defined to be the set of all multiples of the number. Unfortunately, q⋅d is such a multiple of d, so traces rather beg the question.) The Fundamental Theorem of Arithmetic provides constructive help when it's feasible to factor n and d: It offers that d | n if the list of factors of n includes all the prime power factors of d.

Existence of residue quotients is decisively solved by traces, even though traces are unhelpful for real integers.

Uniqueness remains a big issue for modular division. It proved to be no obstacle for real integer division because integers have primes and a property called The Fundamental Theorem of Arithmetic. Problematically, the residue systems of most moduli do not completely support such a theorem.

The (euclidean-)integer division rule is: Find a solution of d⋅q + r = n, and make up side conditions such as Euclid's 0 ≤ r < d to make q be the quotient. That may seem a bit lame, but the world has survived productively ever since. Interestingly, Euclid's remainders — a mere trick for getting unique integer quotients — actually originated our topic: remainders as a new type of number. And the idea of adding side conditions to the basic equation of division helps with modular quotients as well.

For modular-division, the founders (Euler and Gauss) parlayed real units along technical lines rather than intuitive lines. For instance, the result creates oddities like numbers equal to their own reciprocals: 1÷17≡17, and 1÷37≡37 (modulo 72). This has striking consequences, like: For any residue r modulo 72 it makes r⋅17 ≡ r÷17 as well as r⋅17² ≡ r. You don't see things like that every day in the "real" world but they're common in the residue world. Such quirks help make residues much more interesting than integers.

What the ur-theorists were struck by was the existence of real integers that can divide all real integers: the so-called units, 1 and -1. They appear to have entirely ignored the fact that each real integer i is part of an infinitely large trace of real integers — the multiples of i — which i can perfectly well divide. A special thing about the units 1 and -1 is that their trace contains all the real integers.

The founders then proceeded to notice that unit-like residues are also present in every residue system: Each unit has a reciprocal such that the product of it times its reciprocal is congruent to 1. Gauss called those unit-like residues units. Because of the recent discovery of more units, this website calls the originals euler units and the others residual units (or modal units because of their deep connection with the modulus). In this section we'll stick with euler units.

Gauss based his version of residue division upon that unit-fluke.

* Residue Division a la Euler and Gauss:

They must have reasoned something like this: Let the quotient n ÷ d be some residue q. The most fundamental property of any quotient is that it is a solution of an equation or congruence like d⋅q ≡ n. Starting with that, we have n ≡ q⋅d, so

n⋅d^-1 ≡ q⋅d⋅d⁻¹.

But d⋅d^-1 ≡ 1 so

n⋅d^-1 ≡ q⋅1 ≡ q.

Thus, they defined dividing n by d to mean multiplying n by the reciprocal of d, i.e.

n ÷ d ≡ n⋅d^-1.

Good news: Euler found some fast and efficient ways to find the value of d^-1 which are still good to this day.

Is it all making sense so far?

This surely should be making sense, since most everything said so far has been fully established number theory for two centuries. It helps if you remember that residues and integers are very different number-systems, and the ancient arithmetic verbs "add", "subtract", "multiply", and "divide" are misnomers in the case of residues.

Consider, for example: The result of adding residues [5] and [7] modulo 10 is [2]--but doesn't adding something result in more? is 2 really more than 5?

Similarly: If you wanted to share 2 things among 3 people, you'd calculate 2 divided by 3, right? If we do it modulo 10 we get [2]/[3] ≡ [4] (mod 10). Try to interpret THAT as sharing 2 things among 3 people! Are we to give each person 4 of the 2 things? Well, yes, in the residue way: If we take 4 things from the original 2, then 2 minus 4 things remain—and 2−4 ≡ 8 (mod 10); we can do it twice more, leaving 8-4-4 ≡ 0, none left—and we did manage to deliver three sets of 4 to our three people, a total of 4 + 4 + 4 ≡ 2 things—which indeed matches the number we originally had.

This may sound like double-talk but it is no embarrassment within the mathematics because actually, residues are technically NOT "an ordered set". "Equal" is well defined (as "congruence") but notions like "smaller" and "larger", "less" and "more", "above" and "below" are undefined.

A mathematician's takeaway from this is that residues and reals are different kinds of numbers, effective to use in different applications. Quite specifically, if accumulation can occur, if less and more are notions that matter, beware of residues. But if residuals, leftovers, periodicity are in some way paramount — then residues might be the numbers to use.

A ship's captain must understand that changing the ship's course by 450 degrees is the same as making a 90-degree right turn: Navigational headings are residues. The ship's First Mate, on the other hand, as logistics officer, must understand that having no fuel oil is different from having m gallons—no matter what modulus m they might be tempted to consider as a way to save money.

So. The answer to the question "Does this all make sense?" is "Well...yes, and sometimes residues are the right numbers to use, and sometimes euclidean integers are the right numbers to use.

Special symbols we use

a | b "a divides b" (residues)
a .|. b "a divides b" (euclidean integers)
a / b "a over b" (residues)
a . /. b or a .÷. b "a over b" (euclidean integers)
= equals (generic)
.=. "is equal to" (euclidean integers)
≡...(mod m) "is congruent to" (residues)
|S| "size of S" (number of members)

Division Clusters — the first step beyond euler units

Gauss got us started, with his euler units^†. He divined that the collection of euler units constitutes a special algebraic system that in later generations came to be known as an abelian group.

^† I call them that, Gauss probably just called them units.

A group is a collection G of objects (residues, say) with an operation (residue multiplication ⋅ say), with the key properties that
(1) if r and s are both in G then r⋅s is also in G;
(2) there is a unique member ω in G with the property that if r in G then r⋅ω ≡ r;
and (3) Each r in G has an inverse r^-1, also in G, such that r⋅invr ≡ ω.

The group is abelian if r⋅s ≡ s⋅r for all r, s in G.

All residue systems contain at least one group — most contain more than one — and that omnipresent group consists of the euler units. But the euler group is only the tip of the iceberg — units themselves are not the complete division story: For that, we need to examine division clusters of residues — they're all important and they're not all groups!

Definition of the key: division clusters

Division Cluster C_r of system Z_m consists of the residues s whose greatest common divisor with m is the same: gcd(s, m)=gcd(r, m).

There is a one-to-one correspondence between division clusters and euclidean integer divisors of the modulus m.

The mod-m residue and euclidean integer c_r = gcd(r, m) is called the center of the cluster, and is the only member of C_r that divides m.

We already met one of the clusters: C₁ is Gauss's group of euler units. Curiously, C_m is a cluster consisting solely of the residue 0, and — depending on a detail of factorization — it too may be a group of units (group of unit?). Be that as it may, C₁ and C_m are the only clusters that exist in every residue system.

Example Z₁₂: The clusters for modulus m=12, showing centers as C-subscripts and ω-values emphasized, are:

C₁={1, 5, 7, 11}_e, C₂={2, 10}_i, C₄={4, 8}_u, C₃={3, 9}_u, C₆={6}_i, and C₁₂={0}_u.

We sometimes call the clusters "modal" because of their central connection — directly via their "centers" — with the structure of the underlying system modulus.

A correct but inefficient computational method for generating a list of a cluster's members derives directly from the definition:

C_r is the set c_r ⋅ C₁ obtained by multiplying c_r by each euler unit.

The method is inefficient because it generates each member of the cluster multiple times. Notice in the Z₁₂ example, for instance, that C₁ has twice as many members as C₃: There are not enough residues in any of the clusters except C₁.

We address this more specifically as a division issue in due course. In the meantime we can see the numerical extent of the inefficiencies by counting the number of members of the various clusters as follows.

The number |C₁| of residues in C₁ is calculated using the totient function φ(m) later named Euler's Phi function. If c_r ≠ 1 then the size of C₁ is always a multiple of |C_r| — the multiple is almost always by 2 or more, the only exceptions occurring when 2 is a residual unit and |C₂|=|C₁|. Using Euler's totient function again, the size of C_r is |C_r| = φ(m .÷. c_r). It's worth noting that if c_s > c_r and if C_s and C_r are on the same trace with C_s being farther along the trace towards C_m then again |C_s| ≤ |C_r| with |C_r| being an integer multiple ≥2 larger — even though φ(m) is itself not monotonic.

Anyway, |C₁| is larger than |C_r| by the factor φ(m) .÷. φ(m .÷. c_r).

↑ back to menu

Clusters and Chinese Cubes

A Chinese Cube for Z_m is actually a "hyper-rectangle in euclidean integer n-space where n is the number of distinct prime divisors of m" — but "cube" is so much easier to say. Such cubes provide excellent displays of Z_m when n≤3. Here's the n=2 cube for Z₃₆:

Chinese Z36 CubeNotD

Units colored, Omes bold, Ints white

The nine clusters of Z₃₆ are outlined in the figure, and the numeric omes of the four unit clusters are shown in bold font. Note that when the number of prime power factors of m=36 is n=2 then the n-dimensional hypercube is a simple 2-dimensional rectangle.

The two prime power factors of 36 are 2² and 3²; in the Z₃₆ example the residue system Z₄ for one of those factors provides the row labels for the cube and similarly Z₉ for the other provides the column labels. Those labels are themselves 1-dimensional Chinese Cubes — i.e. straight lines for moduli with single prime powers — and their residues are listed in the order of euler units first, then the residual integer power stack in ascending exponent order, and finally the residual unit at the top of the power stack.

Each of the 36 residues of Z₃₆ has its place in the cube — the locations are precisely specified by the Chinese Remainder Theorem, in terms of the row and column labels. Because the orderings of those labels reflect the divisibility structures of the single-factor systems Z₄ and Z₉, the resulting 2-cube strongly reflects the divisibility structure of Z₃₆. Because of the row and column ordering, the cluster of Z₃₆ euler units is at the upper left, occupying some of the lefthand edge and of the top edge of the cube; the cluster of units with ome 9 — together with all the other clusters whose residues it can divide — occupies the entire righthand edge; the cluster of units with ω=28 — and all the clusters of residues it can divide occupies all of the bottom edge; and — also as always — C₃₆={0} is at the bottom right corner.

Almost as important as clusters are their "traces": The trace T_r of division cluster C_r is the collection of all residues t of the form t ≡ x ⋅ s where x is any member of C_r and s is any residue modulo m.

The trace of a cluster contains all the residues of the cluster and usually more.

The trace of a cluster is important because it turns out to be the complete set of all residues that can be divided in a broad sense^♦ by the residues of the cluster.

With reference to 2-dimensional Chinese CUbe graphics, the closest boxes in the trace of a given box are: the neigboring box just below and the neighboring box just to the right of the given box. The trace continues, always down and to the right of each box in the trace, ending with the 0-cluster at the bottom-right corner. Summary, good for any number of dimensions: The given box is in its own trace; and for each box in the trace, all neighboring boxes that are closer to the 0-box are in the trace.

^♦

That's true "in a broad sense", but the best version of division — (i;u)-division — breaks the trace of a cluster of pure residual integers with center c into three parts:

(i,0-denominator traces)

Traces — modified for (i,u) — shown darkened

First, the power stack of clusters with centers from c¹ up to and including c^k-1 where c^k is the center of the unit cluster at the top of that power stack of integer clusters;

Second, the entire face of the particular Chinese cube which contains that particular unit cluster and includes its merger with all the other integer traces of the residue system; and

Third, the region where the first part of the trace merges with all the other integer-or-unit traces.

The first part of the trace is divisible by the particular integers in question, and the second part only by the top-of-stack units along with all other integer clusters. This part contains pure integer clusters and mixed integer×unit clusters, but no pure unit clusters.

Uniquely, the trace T₁ of the group of euler units contains every residue in the modulo-m system—that's why euler units can divide every residue in the system. A handy test of whether any given residue is divisible by the members of a given cluster is:

If r is a unit then residue x is in T_r if and only if ω_r ⋅ x ≡ x (mod m).
Curiously, the product ω_r ⋅ x is always in T_r regardless of whether or not x is in T_r.
If r is not a unit then residue x is in T_r if and only if c_r euclidean divides c_x. That is to say, gcd(r,m) .|. gcd(x,m).

Example traces:
For modulus 12 the traces of the clusters are:
T₁={all the residues mod m}, T₂={2, 4, 6, 8, 10, 0}, T₄={4, 8, 0}, T₃={3, 6, 9, 0}, T₆={6, 0}, and T₁₂={0}.

The shadow of a cluster contains just "the usually more", i.e. members of the cluster's trace that are not in the cluster. The list of shadows might clarify discussion of traces by omitting the duplication.

Example shadows:
For modulus 12 the shadows of the clusters are:
S₁={all residues except those in C₁}, S₂={4, 6, 8, 0}, S₄={0}, S₃={6, 0}, S₆={0}}, and S₁₂=Φ (the empty set).

Definition: units

From the perspective of modular division there are three distinct kinds of residues: units, integers, and mixes.

Residual units are the residues whose division cluster is an abelian group.
We use the adjectives "modular" or "residual" in contexts that might confuse these units with eulers or with euclidean integer units.

It follows from the definition that residual units have inverses, and each kind of unit has its own ω to fit its role in u⋅u^-1≡ ω and ω/u ≡ u^-1. This allows them to play roles similar to the euler units. Gauss's definition of modular Division using euler units applies with one small change to all units. We spell it out here:

* Modular Division by any unit:

We start the derivation the same as for euler units: Let the quotient n/d (equivalently n÷d) be some residue q, where d is any residual unit. Following Gauss, we define the quotient q to be n⋅d^-1.
This almost satisfies the fundamental division requirement that d⋅q ≡ n. Instead, it yields

d⋅q ≡ d⋅(n⋅d^-1) ≡ n⋅(d⋅d^-1) ≡ n⋅ω_d.

What it takes to close the deal is for n⋅ω_d to be congruent to the numerator n. The way we choose to accomplish that is to impose the following side-condition for divisibility of n by d:

By definition, d | n (i.e. unit denominator d divides numerator n)
if and only if the numerator n is in the trace T_d,

i.e. if and only if n ⋅ ω_d ≡ n.

(Note, the divisibility condition is automatically satisfied if d is an euler unit.),

Is residue r a residual unit (mod m)? An easy test:

r is a unit if and only if gcd(r, m) ≡ gcd(r², m).

Example: gcd(16,72)=gcd(256,72)=8 so 16 is a residual unit in the cluster C₈.
Example: gcd(14,72)=2 ≠ gcd(196,72)=4 so residues in cluster C₂ are not units.
Example: gcd(72,72)=gcd(5184,72)=72 so residue 72 is a residual unit in cluster C₇₂.

How calculate the inverse and the omega of a residual unit u?

Calculate the successive powers u, u², u³, …
until the first time u^k ≡ u for some euclidean integer k
which occurs if and only if u is a residual unit.
Then ω_u is u^k-1 and the inverse u^-1 is u^k-2.

Example: The power sequence for 16 (mod 72) is 16, 40, 64, 16 so k = 4, ω₁₆ ≡ 64, and 16^-1 ≡ 40.
Easily confirm by calculating u⋅u^-1≡16⋅16^-1≡16⋅40≡ 64 ≡ ω₁₆.
Other methods require computing the prime factorization of the modulus. It is a benefit that the above algorithm does not.

↑ to menu

Applications of modular division by units

1. 16⋅x≡56 (mod 72), x=?

Solution: ω₁₆≡64 and 64⋅56≡56 so 16 | 56.
Thus x≡56/16≡56⋅40≡8.
Confirm: 16⋅8≡56? yes.

2. 16⋅x≡58 (mod 72), x=?

ω₁₆⋅ 58 ≡32≠58 so 16 does not divide 58, the quotient 58/16 is undefined, and 58⋅16^-1 is meaningless.

3. 5⋅x ≡549 (mod 551), x=?

Solution: 5 is an euler unit so it does divide 549,
and 5^-1≡441 so x≡441⋅549≡220.
Confirm: 5⋅220≡549? yes.
This congruence had only one solution because the denominator 5 was euler (mod 551).

4. 5⋅x² ≡549⋅x (mod 551), x=?

Comparing this with the preceding example it is clear that x=0 and x=220 should both be solutions; not so clear is that there are other solutions as well ... and if euler units were the whole story of units, there would be just two.
In problems like this there's always the possibility of one solution in each division cluster. This modulus is the product of two simple primes (551=19⋅29) so there are four clusters, each consisting entirely of units: C₁, C₁₉, C₂₉, and C₅₅₁.
Multiplying the congruence through by the not-yet-known inverse of x yields: 5⋅x ≡ 549⋅ω_x which is one equation and one obscure relation and two unknowns.
We don't know x yet, but we do know that its omega is one or another of ω₁=1, ω₁₉=494, ω₂₉=58, ω₀=0. We can assume those ω-values one at a time, solve for x, then reject x if is in the wrong cluster i.e. has the wrong omega. For instance, if we assume x is in C₁₉ then the congruence to solve is
5⋅x ≡ 549⋅494 ≡ 114, which yields
x=114/5≡133.
Assuming C₂₉ yields x ≡ 87, C₁ yields x ≡ 220, and C₅₅₁ naturally yields x ≡ 0 :-)

Complete quadratic equations, a⋅x²+b⋅x+c ≡ 0 (mod m), even with only a single unknown, are an order of magnitude more difficult than the above examples.
If we multiply through by x^-1 what remains is still quadratic: a⋅x+b⋅ω_x+c⋅x^-1 ≡ 0, so it doesn't help.
There are some special cases where I can see how to proceed. The most obvious case is when the integer discriminant disc=b²-4ac is an integer square, where we can adapt the quadratic formula to the modular problem. For example:

5. x²+x−12 ≡ 0 (any modulus)

The euclidean integer discriminant b²−4ac=49=7⋅7 so it is a square and euclidean integer solutions exist. They are x = (−1±7) / 2 = 3 or −4. Amazingly, those two are among the solutions for all residue systems!
Translated into modulo 72, for example, the congruence to be solved is:
x²+x+60 ≡ 0 (mod 72),
and its complete list of solutions is:
x≡3 in C₃, 12 in C₁₂, 59 in C₁, and 68 in C₄.
Of course x ≡ 3 and 68 (≡−4) are shared with the euclidean case so they were expected, but...
...where did 12 and 59 come from? Example 6 answers that.
After considering a derivation of the modular quadratic formula it's a surprise that
the quadratic formula found any solutions at all!
We discuss "Example 5" issues further after considering division by non-units.

The next example is one where the integer discriminant b² − 4ac is not an integer square — but the modular discriminant b² − 4ac (mod 663) is a modular square — so: blindly applying the quadratic formula might still work on the modular problem.

6. x²+26x−17 ≡ 0 (mod 663) (663=3⋅13⋅17.)

The discriminants are disc = 744 (int) ≡ 81 (mod 663). 744 is not square, so the euclidean integer version has no (euclidean integer) solutions but, taking the quadratic formula x = (−b ± √(b²−4ac))/2a literally, while calculating it as modular arithmetic, yields
x ≡ (-26 ± 9) / 2 ≡ 314 and 323 — a partial success.
The actual complete list of modular solutions is: x ≡ 119 in C₁₇, 314 in C₁, 323 in C₁₇, and 518 in C₁. We expected 314 and 323 but where did the other two come from?
Answer: We thoughtlessly took √81 to be simply ±9, but Z₆₆₃ contains those along with ±264 as the four square roots of 81 (mod 663) — all four are in C₃. They produce the unexpected extra solutions for Example 6. The same observation serves for Example 5 as well.

The next example is one where neither the integer discriminant nor the modular discriminant is square, but the quadratic equation still has solutions.

7. [haven't found an example yet, nor proven that none exist — here's how close we've gotten.]

Summary

Applications of modular division by residual units leave much to be explored, but that kind of modular division itself is in pretty good shape. If the prime factorization of a modulus contains nothing but distinct primes then all the residue in the corresponding residue system are residual units. If any repeated factors occur then the residue system also contains residual integers, which are a different kind of animal.

Definition: non-units

Residue r is not a residual unit if r² is not in the same residual cluster C_r as r. The most distinctive alternative is that r might be a residual integer. The other possibility is that r is mixed — the product of a residual integer times a unit that is non-euler.

residual integers are quite unlike units: They have no inverses — and their clusters don't have any omegas so there's not even anything to base a notion of inverses on. In division they behave much more like euclidean integers: Specifically, suppose you keep dividing by the same residue r in a division sequence like
s₀, s₁ ≡ s₀ / r, s₂ ≡ s₁ / r, s₃ ≡ s₂ / r, …
When r is a residual integer the sequence usually terminates at some s_k which r cannot divide. When r is either kind of unit, residual or euler, the sequence never reaches such a stopping point: it eventually enters a repetitive cycle of units.

Divisibility in general: A simple rule we are about to explore is: Unit or integer, residue r is able to divide residue s if and only if the center c_r divides the center c_s with 0 remainder (using the euclidean algorithm '.÷.' for integer division).

Finding all quotients — all solutions, that is, of the division-defining congruence d⋅ q ≡ n (mod m) — is the other main key to modular division q ≡ n / d :

If d not.|. n, i.e. d does not divide n — which is to say, the center c_d does not euclidean divide the center c_n — then there are no solutions of the original congruence.

Otherwise, the trick to finding all "quotients" is to use euclidean integer division to remove the common factors c_d = gcd(d,m) from both sides of the congruence. This reduces d⋅ q ≡ n (mod m) to e_d ⋅ q ≡ n .÷. c_d (mod μ) where e_d = d .÷. c_d is an euler and μ = m .÷. c_d is a smaller modulus. We know e_d is an euler unit since it results from removing all the prime factors that d shared with m.
Since euler units divide all residues, e_d modular-divides n as well as it modular-divides n .÷. c_d and division by that euler unit provides a first solution — a "starter quotient" — call it q_o where:
q_o ≡ e_d^-1 ⋅ (n .÷. c_d) (mod μ).
Since i⋅μ is congruent to 0 (mod μ) but not 0 (mod m) until i reaches c_d, we see that the set
q_oΔμ = { q_o + i⋅μ for i = 0,1,..., c_d -1} (mod m)
provides the complete set of quotients modulo m.

The divisibility condition necessary and sufficient to guarantee the existence of solutions q for d⋅q ≡ n (mod m) was shown to be simply that the center of C_d must divide the center of C_n.
It was also shown that the number of distinct solutions is c_d so, unless c_d is 1 — meaning, unless d is an euler unit — then the quotients that exist are not unique.

Example divisibility: Residue 58 divides 56 (mod 72), but 58 does not divide 69. That's because c₅₈=2, c₅₆=8 and 2 .|. 8, but c₆₉=3 and 2 does not euclidean divide 3 (the euclidean remainder of 3 .÷. 2 is 1, not 0). As intended, this shows that not every residue can divide every residue.
Example uniqueness: 58/17 ≡ 50 (mod 72) and quotient 50 is uniquely defined — there is no residue except q ≡ 50 that satisfies the congruence 17⋅q ≡ 58 (mod 72) — which is because 17 is an euler. On the other hand, 58/50 presents an issue: x=17Δ36 so x=17 and x=53 both satisfy the defining congruence 50⋅x ≡ 58 (mod 72) and they can't both be the quotient. We need some rational way to reject all but one of the alternative quotients, something along the lines of Euclid's requirement that the remainders of his divisions must fall between 0 and the diminished denominator. But, wait...

Uniqueness achieved! The ambiguity originates with euler units that are transparent to the center of the denominator; the culprits are the euler solutions of the congruence c_d⋅e ≡ c_d. There is a direct remedy: Organize the division algorithm to form q_o as n⋅(e_d)^-1, then form the full quotient as q .=. (q_o .÷. c_d). Since c_d divides c_n, the particular aspect of c_d that makes the ambiguity invisible in d is also present in c_n and — with this proposed organization of the calculation — it still remains present in q_o because it hasn't yet been removed by the euclidean division of c_n by c_d.

Postpone the congruence solution examples,
later adapt them from c,e to i,u

Our approach to extending modular division into non-unit denominators entails factoring the operands — but not into anything like prime factors. There are many factorizations of residues into products of other residues but two in particular stand out in importance: the (c;e)-factorization and the (i;u)-factorization. All residues admit both.

One of those factorizations was the basis for the preceding introduction to modular division, and we formalize it here:

The (c;e)-factorization of residue r expresses it as the product r ≡ c_r⋅e of the center c_r of its cluster times an euler unit e.
The c and e of (c;e) are just multiplied to produce r but we use the semicolon ';' instead of the center-dot '⋅' because (c;e) is an ordered pair: As products (c⋅e) and (e⋅c) are the same but as factorizations (c;e) is not the same as (e;c) — the center is always mentioned first.
The center is of course unique, but the euler factor is not. The number of distinct alternatives for the euler can be calculated using the Euler Phi function as |c_r;e_r| = |C₁| .÷. |C_r|. The list of residues to choose those eulers from is of length c_r, often more than |c_r;e_r|.

Calculating the "c" of the (c;e) factorization of any residue r is easy: c_r is simply the greatest common divisor gcd(r,m).
The euler factor is a bit trickier. Define e_o = r .÷. c_r and δ = m .÷. c_r. Then (c;e)'s euler factors must be selected as any euler member of the set e_oΔδ which is shorthand for
{e=e_o+i⋅δ ∀ integers i=0, 1, 2,..., c_r-1}.
Notice, the number of quotients to choose from is c_r, but the number of eulers to choose is |c_r;e_r| = |C₁| .÷. |C_r|, which is often less than c_r.
Example (c;e) mod 72
48 ≡ 24⋅5.
Another example (c;e) mod 72
48 ≡ 24⋅11.
OK, the whole example with c₄₈=24, e_o .=. 2, δ .=. 3, and |c₄₈;e₄₈| .=. 12
2Δ3 = {2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71}
whose euler subset is {5 11 17 23 29 35 41 47 53 59 65 71}
so (c₄₈;e₄₈) ≡ 24⋅{5 11 17 23 29 35 41 47 53 59 65 71} — a far cry from being unique!

The modular "(c;e)-quotient"

Early version: To divide n by d we euclidean-divide c_n by c_d to get the core factor c_q of the quotient; then we unit-divide e_n by e_d to get the euler factor e_q of the quotient — or we can do eulers first then centers, it makes no difference. Multiplying the (c;e) factors yields the quotient q ≡ c_q⋅e_q.

Unique quotients version: To divide n by d first (c;e)-factor d and multiply n by the euler inverse e_d^-1 to get q_o; then euclidean divide q_o by c_d to get q.

The "early" version guarantees that q ≡ n / d exists, but the "uniqueness" version guarantees the quotient is unique since the choice of eulers no longer affects the quotient.

But wait... again...
...there is yet another way for (c,e)-division to go wrong — and this fault blows (c;e) out of the water: Sometimes the euler factor, as calculated by the euclidean division e = r .÷. c_r , turns out not to be an euler! but (c;e) depends upon euler which enables it to divide any numerator.
Example 'e' not an euler — Consider two residues modulo 360:
r₁ = 104 ≡ (c,e):8⋅13.
r₂ = 208 ≡ (c,e):8⋅26.
The e-factor 13 of r₁ is truly an euler unit, but that factor 26 of r₂ is a residual integer. The prime factorizations of m and of the two residues is revealing:
m = 2³⋅3²⋅5 r₁ = 2³⋅13 and r₂ = 2⁴⋅13.
The exponent of prime 2 in m is k = 3, in r₁ it is j₁ = 3, and in r₂ it is j₂ = 4.
The fact that j₂ exceeds k is the problem: The exponent of any prime p in the center c of the cluster the unit shares with other units will always match that prime's exponent k in m, even when the exponent in the unit exceeds k, as j₂ does in r₂.
The result is that the excess exponent i = j−k will always get transferred to what was supposed to be the euler factor in a (c;e)-factorization.
We tried moving such excess unit-factors back into c where they belong, but the result is that the enlarged value of c in a denominator may no longer divide its counterpart in the numerator — even when numerator and denominator are in the same division cluster!.
Unless a solution is discovered, (c;e)-division must be (as Apple's Xcode would put it) deprecated.

Move "Intro to q<>d" somewhere below (see Example q,d-symmetry)

The deprecated (c;e)-division has another peculiarity: It makes no reference to residual units! We're not that sad to see it be forced out.

Maybe this next factorization is better? Focussing directly upon the interplay between residual integers and residual units, it surely seems more fundamental.

(i;u)-factorization expresses r as r ≡ i_r⋅u_r where i_r is a residual integer and u_r is a unit.

The "integer factor of r" is 1 if r is just a unit; otherwise i_r is a unique residual integer; in either case, a starter value for "the unit factor of r" is extracted from r by the euclidean integer division u_ro = r .÷. i_r.

The number of distinct alternative units for r is simply |i_r;u_r|=i_r itself. The complete list of those alternative units is u_roΔ(m .÷. i_r). Note, the reason this works is: i_r ⋅ (m .÷. i_r) = m ≡ 0.

Calculating the integer factor i of the (i;u) factorization is the tricky part. It is easy enough if we can use the prime factorizations of the modulus and its residues — easy enough for modest systems with modulus in the billions, but virtually impossible when the modulus is huge. Our method does not need any prime factorizations.

Example (i;u) mod 72
48 ≡_iu: 3⋅16.
The integer part of the unit u₄₈ is 1 of course, 16 ≡_iu 1⋅16
as is the unit part of the integer i₄₈, 3 ≡_iu 3⋅1)
Another Example (i;u) mod 72
48 ≡_iu 3⋅40.
OK, all the alternatives
48 ≡_iu 3⋅(16Δ24) ≡ 3⋅{16, 40, 64}. There are three alternative units because i₄₈ ≡ 3. We sometimes use the notation w_i for such sets of residues that, kind of like ω-omes-for-integers, are transparent to integer i.

The modular "(i;u)-quotient"

Based on (i;u), another way to divide n by d is to euclidean-divide the integer factors i_q ≡ i_n .÷. i_d of the quotient. Then unit-divide to get the unit factor u_q ≡ u_n ⋅ u_d^-1 of the quotient. Multiplying the two (i;u)-quotient factors yields the quotient q ≡ i_q⋅u_q.

The (i;u)-quotient's divisibility condition d |_iu n requires that i_d .|. i_n AND u_d | u_n, which means i_d euclidean-divides i_n with 0 remainder AND ω_{u_d}⋅ u_n ≡ u_n.
This shows that the (i;u)-quotient q ≡_iu n / d exists.

Uniqueness, just as with (c;e)-division, is achieved by re-arranging the calculation to preserve the overlap of the transparency-sets w_in and w_id :
First calculate q_o = n⋅u_d^-1 then complete the division as the euclidean quotient q = q_o .÷. i_d.

(i,u) division works quite like (c,e) — sometimes with different quotients — but the big difference is in their definitions of divisibility: (c,e) says what I've preferred all along, that d | n when c_d .|. c_n, while (i,u) on the other hand requires i_d .|. i_n, which prevents integers from dividing units — they can't even divide the units at the top of their own power stacks, for instance 2 (mod 72) divides every residue in C₂ and in C₄ with both factorizations, but 2 also (c;e)-divides the residual units in C₈ while 2 does not (i,u)-divide those units; I like that the behavior of (i;u) is totally consistent with euclidean integers — which don't divide their units ±1.
I hate that (c;e) totally ignores division by residual units — actually badly stumbles on it — but I also hate the thought of giving up the perfect (c;e) version of divisibility.

↑ to menu

Applications of modular division by residual integers
With (i;u)-division we can take a further look at quadratic congruences. One algebraic approach reduces a quadratic equation into a simple square-root problem, and adapts readily to modular:
Re-cast x² + br + c ≡ 0 (mod m) into the form (x + β)² + γ = x² + 2βx + (β² + γ) ≡ 0.
The forms are equivalent if β ≡ b/2 and γ ≡ c − β².
Knowing β and γ we find x from the modular square root of −γ.

There are just three issues that could get in the way of this process: First, b might not be divisible by 2 (mod m). Second, −γ might not be a square (mod m). Third, how are square roots for residues with composite modulus?

Modular square roots are an issue on their own. Around a century ago some modular sqrt algorithms emerged, but only for prime moduli. When m is composite, much remains to be discovered so we need to take square roots case by case. For exploratory convenience I've been relying on an easily written little "brute-force" complete-search applet that simply evaluates any target quadratic at every residue in the system and notes which satisfy the congruence.

The residue system Z_m is much more complicated than the euclidean integer system Z and many more surprises wait to be stumbled upon.

Applications of modular division (cont'd)

8. x²+x−12 ≡ 0 (mod 72) (Example 5 revisited)

Modular division fails at β = b/2 because in Z₇₂ the center c₂=2 does not euclidean-integer divide the euler center c₁=1.
Looking back at Example 5 we see: This same equation with same modulus was found to have four solutions.
Residues...surprises...you know to expect.

9. Same as Example 8, but m=63 this time.

As modulo 63 residues, 1 and 2 are both in the same cluster so each divides the other. In particular, β ≡ 1/2 ≡ 32 (mod 63).
Next we find γ ≡ 35 (mod 63) thence x+β ≡ √28. This doesn't look promising to a euclidean-integer-trained eye but, in fact, 28 has two square roots: 28 and 35 (mod 63). So both x ≡ 3 and x ≡ 59 (≡ -4) are solutions. In fact, these are the only two solutions for this modulus. How do I know that? I wrote a small brute-force applet called "Solve Modular f(x)≡0" that searches all residues for solutions. That's how I'm doing all the modular square roots too, since the moduli of most residue systems I care about are not prime, they're products of powers of primes.

10. 35x²+35x-12 ≡ 0 (mod 63)

Search found no solutions, but the discriminant disc=b² − 4ac ≡ 7 (mod 63) — and 7 (mod 63) truly is square, with roots 14 and 49 (mod 63). Does x≡(-b±√disc)/(2a) ≡ (-35 ± 14)/7 ≡ 14 and 56 not yield two solutions? It does not! for instance 35⋅56²+35⋅56-12≡9 not ≡0.

IMPROVEMENTS PENDING FROM HERE ON...

Integer division ambiguity ...
... has been resolved as of May, 2022.

Further background on modular arithmetic

Frrraction is a product of GRS Enterprises, NLC,
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.