This website is supported by the iPhone app called Frrraction.

Current with Frrraction Version 0.96.13

- Residues: What they are
- The Modular Circle
- Names of residues
- Negative residues
- Modular arithmetic
- The math ops + and −
- The math ops • or × and ÷ or /
- Division — history
- Does it make sense so far?
- Special symbols we use
- iu-Division — overview
- iu — The key to division
- iu — factorization
- iu:division — raw
- iu — the last ambiguity
- iu:division — refined
- iu — q ↔ d symmetry
- iu — conclusion
- iu-Division — deep dive
- Integer division ambiguity

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

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

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 menuWhen '`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.

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 menuDivision 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^{2} ≡ *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

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

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

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
*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^{†}.

^{†} Euler units comprise the algebraic group C_{1} defined by gcd(*d*, *m*)=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(*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.

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): q_{1}=n/d, q_{2}=q_{1}/d, q_{3}=q_{2}/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 Z_{48}, 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^{3} and their associates^{†} are integer-like in Z_{48}, 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*.

^{†} Actually, if *r* is integer-like then gcd(*r*⋅*r*, *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*, *p*^{2},..., *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 Z*m*, 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, r^{2}, r^{3}, ...

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

C

whose

The notation correctly implies that if s is a member of C

*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}.

**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 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_{ir} 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 Ë_{ir} of euler units ë whose members are transparent^{†} to r and, more importantly, transparent to i_{r}. Residue 1 is always in Ë_{ir}, whose total number of members
is the integer i_{r} itself.

^{†} "Transparent" is used here in the sense that if ë is in Ë_{ir} 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 Ë_{ir} 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.

**Modular iu:division**, the raw idea

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 Ë_{2}={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_{105} is due to Ë_{3}={1,121,241}, and the issue is that its members can convert u_{105} into ë⋅u_{105} = 1⋅u_{105}≡35 or 121⋅u_{105}≡275 or 241⋅u_{105}≡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).

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

↑ to menu**There is one final ambiguity**

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 Ë_{in} transfer to u_{n} the same way the eulers in Ë_{id} transfer to u_{d}. The transparency of Ë_{in} can be damaged if divided by i_{d} So,⋅⋅⋅

**Modular iu:division**,

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 Ë_{id} 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 Ë_{id} ; 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 Ë_{id} and Ë_{in} 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:

q = n/d ≡_{iu:}[n⋅inv(u_{d})] . /. i_{d}.

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}: ω_{ud}=145, u_{n}⋅ω_{ud}=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.

**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 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^{2},⋅⋅⋅, 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^{2} ⋅ 3^{2} has the prime-power stacks 1,2,4,8 and 1,3,9. Division cluster
C_{20}={4,20,28,44,52,68} has center c_{20}=4 and Size(C_{20})=6; cluster
C_{26} has center c_{26}=2 and Size 12.

The smallest 6 members of C_{26} are {2,10,14,22,26,34}.
So c_{26} < c_{20} < 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_{26} — 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**Conclusion**

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.

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.

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.