to the Main Frrraction Guide→

Mod m Introduction

This website is supported by the iPhone app called Frrraction.

Current with Frrraction Version 0.96.13

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.

 ↑ to menu

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.

 ↑ to menu

Names of residues

Each residue r modulo m is technically defined to be a list of infinitely many common (that is, euclidean) integers: ⋅⋅⋅, r–2m, rm, r, r+m, r+2m, ⋅⋅⋅ — any of which can be used as a specific name (label) for r. Among that plethora of synonyms there is just one that falls in the range 0 ≤ r < m. That unique label is described as the residue's remainder or its 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 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.

 ↑ to menu

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.

 ↑ to menu

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.

 ↑ to menu

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.

 ↑ to menu

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.

 ↑ to menu

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, qd 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 dq + 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⋅172 ≡ 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 dq ≡ n. Starting with that, we have n ≡ qd, so

nd-1 ≡ qdd−1.
But dd-1 ≡ 1 so
nd-1 ≡ q⋅1 ≡ q.

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

n ÷ d ≡ nd-1.

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

 ↑ to menu

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.

 ↑ to menu

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"
Cr cluster containing r
cr center gcd(r,m) of Cr
|S| "size of a set S" (number of members)

 ↑ to menu
Birkhoff and MacLane
The First Problem

The original solution of the congruence dq ≡ 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.

Euler units comprise the algebraic group C1 defined by gcd(dm)=1.

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(dm)>1. The ambiguity occurs because that number gcd(dm) is also the number of distinct residues q that solve the defining congruence dq ≡ n (mod m) — and quotients should never be ambiguous.

 ↑ to menu

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

  DSQ(n,d): q1=n/d, q2=q1/d, q3=q2/d,...

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 Z48, 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 23 and their associates are integer-like in Z48, 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(rr, m)= gcd(r, m); otherwise r is integer-like.

Actually, if r is integer-like then gcd(rr, m) > gcd(r, m).

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, p2,..., pk.

"Maximal" in the sense that, while pj divides m for all 1 ≤ jk, pk+1 does not.

Corollary 1a:   In that notation, pk is a unit, and each pj for 1 ≤ j < k is an int of Zm. 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):

  PSQ(r)=r, r2, r3, ...

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 ru ≡ 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 32u ≡ 32 for u=3; similarly PSQ(3)=3,9,27,81,51,57,75,33,3... which returns to 3 at 3u 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".

Definition: Each residue r in Zm is a member of a particular division cluster
  Cr = { s in Zm | cs = cr }

whose center cr — the integer gcd(r,m) — is the only member of Cr that euclidian-divides m.
The notation correctly implies that if s is a member of Cr then Cs and Cr are the same set.

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

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

Division clusters provide residue systems with a comprehensive structure and deserve an article of their own. Their importance is established by
Theorem 3:

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

and by its
Corollary 3: Units always have inverses; ints never have inverses.

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

 ↑ to menu

Division by unit denominator

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.

Division by int denominator

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

Division by composite denominator: iu-factorization

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

Note: Cir and Cr are generally different sets.

There are simple algorithms to construct ir, and the value is unique. With ir in hand, r . /. ir is one of the values of ur , 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 ur is ambiguous unless ir ≡ 1. That's because there is an algebraic group Ëir of euler units ë whose members are transparent to r and, more importantly, transparent to ir. Residue 1 is always in Ëir, whose total number of members is the integer ir  itself.

"Transparent" is used here in the sense that if ë is in Ëir then ë⋅r ≡ r and ë⋅ir ≡ ir .

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

 ↑ to menu

Modular iu:division, the raw idea

The plan of the raw version of iu:division is to separately check the divisibility condition for ints id .|. in and for units ud | un. Then separately do the divisions to obtain partial quotients qi .=. in . /. id and qu ≡ un/ud. Finally, multiply the two partial quotients to get q = n/d ≡ qi⋅qu.

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 = ir⋅ur = 2⋅5. As discussed above, the group of eulers transparent to ir=2 is Ë2={1,7} so 2⋅1≡2⋅7≡2 but, as forewarned, those eulers are not all transparent to ur: ë=1 is transparent of course, but ur⋅7=35≡11≠ur so ë=7 is not transparent to ur. 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⋅ud) 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 un would only make matters worse) — then if we attempt to formulate 6/10 as (2/2)⋅(3/ud) we find: 2 is an int so 2/2 is unambiguously 2. /.2=1 — so the quotient 6/10 equals the partial quotient 3/ud, which is either 3/5=3⋅inv(5)=3⋅5≡3 or 3/11=3⋅inv(11)=3⋅11≡9: the ambiguity in ud (induced by id not being 1) was transmitted via ë⋅ud via inv(ë⋅ud) 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 iq=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=iq⋅uq=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 u105 is due to Ë3={1,121,241}, and the issue is that its members can convert u105 into ë⋅u105 = 1⋅u105≡35 or 121⋅u105≡275 or 241⋅u105≡155, whose inverses are 35, 155, and 275 respectively.
 If we accept for the moment that 5 (the natural value of un) is correct then uq= un⋅inv(ud) can thus be any of un⋅35≡175 or un⋅155≡55 or un⋅275≡295; completing the calculations of quotient q by multiplying those three values of uq by iq=4 yields q = iq⋅175 ≡ 340 or iq⋅55 ≡ 220 or iq⋅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).

Fortunately, there is a way around this problem. But first,⋅⋅⋅

 ↑ to menu

There is one final ambiguity

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

 ↑ to menu

Modular iu:division, refined

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

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

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

Lemma: If b is an int and b .|. a, then b .|. (ac) 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 Ëid and Ëin ambiguity problems is threefold: Use the unique natural unit factor for ud; keep in unchanged and still connected to un within n — until after un has incorporated inv(ud) while still connected to (never disconnected from) in; finally, do the euclidean division by id to complete the production of q. Formally:

    q = n/d ≡iu:[n⋅inv(ud)] . /. id.

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.
ud does divide un: ωud=145, un⋅ωud=5⋅145≡5=un;
and id does euclidian divide in: 12 . /. 3 = 4 with 0 remainder.
so q≡iu:(60 ⋅ 35). /.3≡(300). /.3 = 100. Unambiguously.

 ↑ to menu

Progress on q ↔ d symmetry

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

a⋅b ≡ a⋅c implies b ≡ c.

An equivalent statement is:

The congruence a⋅x ≡ a⋅b has x ≡ b as its unique solution.

Another is:

If r ≡ a⋅b then r/a ≡ b and r/b ≡ a.

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.

Better framed in the context of modular division is a property we call

  quotient ↔ denominator symmetry

and abbreviate as q ↔ d:

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 Zm unless m were prime — the violations seemed incoherently scattered among n/d ratios.

The issue is not new to modular arithmetic. In the Gauss "e formulation" of division, only euler units (residues co-prime with the modulus) could be denominators, but q ←e→ d then required both n and d to be euler units because, if n isn't euler then q ≡ n⋅inv(d) is also not euler, so q didn't e-divide n and q ←e→ d was out of the question.

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.

Theorem 7: If n is a residual (non-euler) unit but d is an euler unit then (n,d,q) does NOT show 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 cn and cd of the division clusters Cn and Cd are in Zm's same prime-power stack ( p, p2,⋅⋅⋅, pk ) with 1 ≤ cd ≤ cn < pk, then n/d has q ←iu→ d symmetry if and only if n is in Cn and d is one of the Size(Cn)-integer-smallest members of Cd.

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

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

e.g. m=72=22 ⋅ 32 has the prime-power stacks 1,2,4,8 and 1,3,9. Division cluster C20={4,20,28,44,52,68} has center c20=4 and Size(C20)=6; cluster C26 has center c26=2 and Size 12.
The smallest 6 members of C26 are {2,10,14,22,26,34}. So c26 < c20 < 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 C26 — 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.

 ↑ to menu


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.

 ↑ to menu

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

Frrraction is a product of GRS Enterprises, NLC,
a Michigan company since 1978
Most recent update of this guide: August 22, 2023, 10:00amET
Copyright © GRS Enterprises, NLC, 2010-2023
Not void, even where prohibited. Your mileage may vary.