Mod m Introduction

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.

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

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 supports that custom by providing a special and very efficient instruction — often expressed something like r=mod(i,m) — which replaces any integer i by its modulo-m remainder r. Frrraction uses such a function at the end of almost all its modular computations.

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

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.

* 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)
.=. equals (euclidean integers)
≡ (mod m) "is congruent to" (residues)
≡_e: Gauss's "euler-units-only quotient"
≡_iu: general "iu-quotient"
C_r cluster containing r
c_r center gcd(r,m) of C_r
|S| "size of a set S" (number of members)

The original solution of the congruence d⋅q ≡ n (mod m) was Gauss's quotient q = n/d ≡ n⋅inv(d) (mod m) where the numerator n can be any residue modulo m but the denominator d is restricted to be an euler unit^†.

It was an excellent beginning for modular division, but the situation in that corner of number theory has languished there for nearly two centuries. Even the best attempts to permit other denominators have until now been universally deprecated due to an endemic ambiguity whenever gcd(d, m)>1. The ambiguity occurs because that number gcd(d, m) is also the number of distinct residues q that solve the defining congruence d⋅q ≡ n (mod m) — and quotients should never be ambiguous.

iu: The key to modular division

Residue systems have two distinct kinds of residues: unit-like and integer-like. That's the key.

To see the distinction, assume d divides n and consider the division sequence (DSQ):

If d is unit-like then that sequence of quotients continues forever with valid quotients. (In the real integers there are only two units: 1 and –1 — while residue systems typically have many units.)
If d is integer-like then the sequence ends at some quotient which d does not divide — and the sequence stops; that's the way integers behave, e.g. DSQ(8,2): 8/2=4, 4/2=2, 2/2=1, 1/2=undefined (in the integers).
In Z₄₈, for example, where 3 and its associates^† are unit-like,
iu-DSQ(9,3): 9/3≡3, 3/3≡33, 33/3≡27, 27/3≡9,...
which has looped back and obviously continues indefinitely with all quotients well defined: clearly, that is not integer-like. On the other hand, powers of 2 up thru 2³ and their associates^† are integer-like in Z₄₈, so we have
iu-DSQ(8,2): 8/2≡4,4/2≡2,2/2≡1,1/2≡undefined,
which is perfectly integer-like behavior.

^† The associates of any residue r are the residues computable as s≡r⋅e where e is any euler unit except e=1.

Theorem 1: Residue r is unit-like if and only if gcd(r⋅r, m)= gcd(r, m); otherwise^† r is integer-like.

Subsequently, we drop the annoying "-like" terminology in favor of calling them simply "units" and "ints" (reserving the noun "integer" for its classical sense).

Definition: For each prime divisor p of the modulus m there is a maximal^† prime-power stack p, p²,..., p^k.

^† "Maximal" in the sense that, while p^j divides m for all 1 ≤ j ≤ k, p^k+1 does not.

Corollary 1a: In that notation, p^k is a unit, and each p^j for 1 ≤ j < k is an int of Z_m. The total collection of the system's residues — all m of the units, ints, and composites — consists of the euler units together with these prime-powers for each prime divisor of m, plus all modular products of these with each other.
(As a formula for generating the members of Zm, Corollary 1a is of course severely inefficient, as it tends to generate each member many times over.)

Division sequences, and divisors-shared-with-its-modulus, are two ways that residue r reveals its style of division. Another way is its power sequence (PSQ):

This is significant because PSQ's make no reference, direct or indirect, to division: The existence of ints and units is simply a fact about residues, not an artifact of any particular notion of modular division.

Theorem 2: If and only if r is a unit, its PSQ exponent eventually reaches a value u > 1 where r^u ≡ r.

Every PSQ eventually loops back to some earlier power, creating a cycle that repeats continually thereafter. That's because there are only a finite number of residues in the system. Sometimes the cycle for PSQ(r) includes the starting residue r, sometimes not; that property distinguishes units from non-units.

For example, modulo 96: PSQ(2)=2,4,8,16,32,64,32,64,32,... which loops back and repeats the 32,64-subsequence forever, so obviously the PSQ can never return to 2, a fact that shows 2 to be an int; 4 and 8 and 16 are also only seen once in their power sequences so they too are seen to be ints; but PSQ(32)=32,64,32,... and this reveals 32 to be a unit with 32^u ≡ 32 for u=3; similarly PSQ(3)=3,9,27,81,51,57,75,33,3... which returns to 3 at 3^u with u=9.

Curiously, the cycle itself always consists solely of units. This causes a peculiarity: Somewhere along the PSQ for any non-unit, the division-character of the powers in the sequence changes from non-unit into unit. More generally, for every int r there are ints s (only in the same power-stack as r) such that r ⋅ s is a unit. Products of units × units always yield units, but ints can "shape-shift".

Corollary 1b: Residue r is a member of C_r. All and only the members of C_r can be expressed as modular products s = r ⋅ e where e is some not necessarily unique euler unit for each s. In other words, C_r consists of r and all of its associates.
(As a formula for generating the members of C_r, Corollary 1b is inefficient; it generates each member several times, specifically EulerPhi(m)/EulerPhi(m/c_r) times, which is always 2 or greater if c_r>2.)

Corollary 1c: All members of C_r have the same division-character as r, unit-like or integer-like. This includes its center c_r.

Residue r is a unit if and only if the division cluster C_r is an algebraic group with multiplication (mod m) as its group-operation.

The key parts of the proof are within the sequence PSQ(r): r⋅r^u-1≡r so the unit-group's identity is ω_r=r^u-1; and r⋅r^u-2≡r^u-1≡ω_r so the inverse of r is inv(r)=r^u-2.

Definition: When d is a unit we define q=n/d≡n⋅inv(d) if n and d satisfy the iu-divisibility condition n⋅ω_d≡n (mod m).

Note: Inv(d) is ω_d/d — i.e. n/d with n=ω_d; the divisibility requirement n⋅ω_d≡n is thus ω_d⋅ω_d≡ω_d which is true.
The quotient 1/d is undefined unless d is an euler unit.

Definition: When d is an int at the center of its cluster, we define q = n/d = n . /. d (where the symbol . /. designates euclidean integer division). The int-divisibility condition d .|. n is that the euclidean remainder after dividing n by d be 0.

[Note: In both cases of pure denominator (unit or int) the quotients are unique if n and d are both unambiguously known.]

Theorem 5: Any residue r can be expressed as the product of an int i_r and a unit u_r: r ≡ i_r ⋅ u_r.
If r is a unit then its int-factor is i_r=1.
Otherwise, i_r is the center of its cluster, the solution of i_r=gcd(i_r , m).

Note: C_{i_r} and C_r are generally different sets.

There are simple algorithms to construct i_r, and the value is unique. With i_r in hand, r . /. i_r is one of the values of u_r , called the natural unit factor. Choosing it to make iu-factors unique and then to help make ≡_iu:-quotients unique is analogous to Euclid choosing remainder r = 0 to make euclidean quotients unique.

Although the int factor is unambiguously known and the divisibility-checks do not require the unit factor to be explicitly known, it is the case that u_r is ambiguous unless i_r ≡ 1. That's because there is an algebraic group Ë_{i_r} of euler units ë whose members are transparent^† to r and, more importantly, transparent to i_r. Residue 1 is always in Ë_{i_r}, whose total number of members is the integer i_r itself.

^† "Transparent" is used here in the sense that if ë is in Ë_{i_r} then ë⋅r ≡ r and ë⋅i_r ≡ i_r .

Residue 1 is transparent to all residues but if i_r >1 then some of the eulers in Ë_{i_r} are not transparent to the unit-factor u_r. The intuitive "raw" version of iu:division, defined below, shows vulnerability to this issue, and the "refined" version subsequently resolves the issue.

The plan of the raw version of iu:division is to separately check the divisibility condition for ints i_d .|. i_n and for units u_d | u_n. Then separately do the divisions to obtain partial quotients q_i .=. i_n . /. i_d and q_u ≡ u_n/u_d. Finally, multiply the two partial quotients to get q = n/d ≡ q_i⋅q_u.

Natural, straightforward, intuitive. The very kind of modular division that has eluded us for so long.

But it has ambiguity issues that need to be resolved:

e.g. modulo 12: An iu-factorization of r=10 is r = i_r⋅u_r = 2⋅5. As discussed above, the group of eulers transparent to i_r=2 is Ë₂={1,7} so 2⋅1≡2⋅7≡2 but, as forewarned, those eulers are not all transparent to u_r: ë=1 is transparent of course, but u_r⋅7=35≡11≠u_r so ë=7 is not transparent to u_r. This means the iu-unit factor of r=10 (mod 12) is ambiguously either 5 or 11.
That ambiguity has consequences. For instance, if 6/10=(2⋅3)/(2⋅u_d) were a ratio whose quotient we desired to know — assume we are somehow assured that 3 is unambiguously the unit factor of the numerator (ambiguity in u_n would only make matters worse) — then if we attempt to formulate 6/10 as (2/2)⋅(3/u_d) we find: 2 is an int so 2/2 is unambiguously 2. /.2=1 — so the quotient 6/10 equals the partial quotient 3/u_d, which is either 3/5=3⋅inv(5)=3⋅5≡3 or 3/11=3⋅inv(11)=3⋅11≡9: the ambiguity in u_d (induced by i_d not being 1) was transmitted via ë⋅u_d via inv(ë⋅u_d) into ambiguity in the quotient 6/10. Spoiler alert: As we'll see below, the true iu-quotient is q=6/10≡_iu:3 (mod 12).

e.g. modulo 360: Suppose q is to be 60/105.
The natural iu-factorizations are n=60≡_iu:12⋅5, d=105≡_iu:3⋅35. Then i_q=12. /.3=4 (the unique int-factor of q), and inv(35)≡35 so 5/35≡5⋅35≡175 (a unit-factor of q), so the quotient is expected to be q=i_q⋅u_q=4⋅175 ≡340.
As is well known, there are fifteen distinct solutions q of the congruence 105⋅q≡60 (mod 360), including q=4, q=28, q=52, etc. (keep adding 24); that's the infamous familiar old ambiguity due to gcd(105,360) = 15 ≠ 1 — but ignore that, it is irrelevant here.
The actual ambiguity in u₁₀₅ is due to Ë₃={1,121,241}, and the issue is that its members can convert u₁₀₅ into ë⋅u₁₀₅ = 1⋅u₁₀₅≡35 or 121⋅u₁₀₅≡275 or 241⋅u₁₀₅≡155, whose inverses are 35, 155, and 275 respectively.
If we accept for the moment that 5 (the natural value of u_n) is correct then u_q= u_n⋅inv(u_d) can thus be any of u_n⋅35≡175 or u_n⋅155≡55 or u_n⋅275≡295; completing the calculations of quotient q by multiplying those three values of u_q by i_q=4 yields q = i_q⋅175 ≡ 340 or i_q⋅55 ≡ 220 or i_q⋅295 ≡ 100.
As a check on this work, we confirm the ambiguity by simple multiplication of those values of q by the value d=105: q⋅d = 340⋅d≡60 or 220⋅d≡60 or 100⋅d≡60. They all are solutions of the division congruence. Spoiler alert: The true iu-quotient is q=60/105≡_iu:100 (mod 360).

Isolating the numerator's unit factor u_n from its integer factor i_n before dividing by i_d introduces a separate ambiguity into the quotient n/d≡_iu:q, this one due to i_n. Specifically, the transparent eulers in Ë_{i_n} transfer to u_n the same way the eulers in Ë_{i_d} transfer to u_d. The transparency of Ë_{i_n} can be damaged if divided by i_d So,⋅⋅⋅

Fortunately, there is a way to immunize division against the ambiguity discussed above: The opportunity is provided by the fact that i_d absorbs all members of its associated group Ë_{i_d} of transparent eulers. We can use that fact to neutralize the problem at its very source!

Moreover, i_n shares the absorbency of i_d , since i_n is euclidean-divisible by i_d which means in a very real sense that i_n contains i_d (as a factor) — but... if the i_d factor is removed from i_n in the process of separately calculating i_q then n, deprived of i_d, would no longer be inoculated against the ambiguity caused by Ë_{i_d} ; if that is done then the ambiguity gets carried over to inv_u_d and thence to u_q when multiplying by inv(u_d) in the production of u_q.

The final solution: Don't iu-factor n before multiplying by inv(u_d), and don't iu-factor that result before euclidean dividing by i_d. Leaving the numerator intact in this way is supported by the

Lemma: If b is an int and b .|. a, then b .|. (a⋅c) for any unit c.^†

^† In the real integers, the conclusion of the lemma is true without qualification. In the residual case it needs the qualification that c be a unit. The problem it avoids is that the product of two ints can be a unit — and ints (such as b in the lemma) do not ui-divide units.

In summary, the solution to the Ë_{i_d} and Ë_{i_n} ambiguity problems is threefold: Use the unique natural unit factor for u_d; keep i_n unchanged and still connected to u_n within n — until after u_n has incorporated inv(u_d) while still connected to (never disconnected from) i_n; finally, do the euclidean division by i_d to complete the production of q. Formally:

Note: There are minor variations of this algorithm which are not entirely equivalent but might deceptively seem to be. The present refined iu-division algorithm stands quite alone.

e.g. modulus 360, n=60≡_iu:12⋅5, d=105≡_iu:3⋅35, inv(35)≡35.
u_d does divide u_n: ω_{u_d}=145, u_n⋅ω_{u_d}=5⋅145≡5=u_n;
and i_d does euclidian divide i_n: 12 . /. 3 = 4 with 0 remainder.
so q≡_iu:(60 ⋅ 35). /.3≡(300). /.3 = 100. Unambiguously.

A longtime nemesis of modular division has been the failure of various formulations to have the following widely expected "cancellation property":

Failure of the first two variations is an unavoidable property of any residue system whose modulus is not prime — that is, any residue system that has ints and/or more than one class of units. The third one notably shares with division the responsibility for its failure, which provides a partial escape for more diverse residue systems.

Definition: The ordered triplet (n,d,q) is said to show q ↔ d if d and q each divide n, with n/d ≡ q and n/q ≡ d.
[Note: In the case of iu-division, if either d or q divides n then both divide n with unique quotients, so we often use n/d instead of the triplet (n,d,q) and say "n/d shows (or does not show) q ←iu→ d"].

In past versions of modular division, violations of q ↔ d were common — and for most systems Z_m unless m were prime — the violations seemed incoherently scattered among n/d ratios.

The present "iu formulation" of division has finally rationalized the issue. We can now prove at least three classes of cases:

Theorem 6: If n and d are in the same division cluster (either ints or units) then q ←iu→ d.

That's because, with euler denominator, the quotient q would be in the same non-euler cluster as n, so not possibly congruent to the euler d.

The broadest so far, my favorite, is

Theorem 8: If the centers c_n and c_d of the division clusters C_n and C_d are in Z_m's same prime-power stack ( p, p²,⋅⋅⋅, p^k ) with 1 ≤ c_d ≤ c_n < p^k, then n/d has q ←iu→ d symmetry if and only if n is in C_n and d is one of the Size(C_n)-integer-smallest members of C_d.

It's an awkward mouthful to be sure, but it streamlines our understanding of the vast majority of all n/d ratios.

[Note that p^k — the top of the p-prime-power stack —is always a unit, and ints never iu-divide units, so the strict inequality c_n < p^k is required in Theorem 8. The special case of c_d = 1 and c_n = p^k is covered by Th.7. The special case of c_d = c_n = p^k is covered by Th.6.]

e.g. m=72=2² ⋅ 3² has the prime-power stacks 1,2,4,8 and 1,3,9. Division cluster C₂₀={4,20,28,44,52,68} has center c₂₀=4 and Size(C₂₀)=6; cluster C₂₆ has center c₂₆=2 and Size 12.
The smallest 6 members of C₂₆ are {2,10,14,22,26,34}. So c₂₆ < c₂₀ < 8; so Th.8 explains why 20/26≡_iu:34 and 20/34≡_iu:26 show q ←iu→ d.

58 is another of the residues in C₂₆ — but it is NOT among the integer-smallest 6 of them — so Th.8 also explains why 20/58≡_iu:14 and 20/14≡_iu:22 do NOT show q ←iu→ d.

And there are other cases, involving mixed int⋅unit residues, but they are in the minority. I think the principles are all already in play but I haven't worked out the details yet.

What iu-division amounts to is not just a small pointless collection of isolated definitions. It is a major natural extension of a thread in number theory initiated by Carl Friedrich Gauss in the early 1800's: the treatment of residues as a number system in its own right, not just an adjunct to the system of real integers. It might even find its way to into the growing body of applications of modular number theory.

The following sections of this webpage explore it with greater attention to detail but are not yet fully up to date with this overview. Where differences appear, the overview has it right.

iu-Division — deep dive

Technical background on modular arithmetic

Examines residues from the original point of view: Each residue is just an infinite set of euclidean integers, and Z_m is a collection of m such sets.
Myself, I prefer to think of residues as a nearly independent category of numbers. The older point of view is analogous to focussing on real numbers as infinite series of rational numbers: It's a tool, and sheds some insight, but I find it awkward and distracting.