This website is supported by the iPhone/iPad app called Frrraction.

Current with Frrraction Version 0.96.13

- to the main Residue Intro
- iu-Division — deep dive
- Definition: clusters
- Chinese Cubes
- Definition: units
- Applications of units
- Definition: non-units
- Applications of non-units
- Applications of ints
- Integer division ambiguity

↑ to 'Deep' menu

Gauss got the world started on modular division with his "euler units"^{†}. He saw
that the collection of those particular units constitutes a special algebraic system that in later
generations came to be known as an *(algebraic) group*, the term coined by Everiste Galois.

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

An algebraic *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*⋅inv*r* ≡ ω.

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

All residue systems contain at least two groups — most contain more than two — and the more important of those omnipresent groups consists of the euler units. The other is the trivial group {0,⋅} But those two are only the tip of the iceberg, and units themselves are not the complete division story: For that, we need to examine

* Division Cluster* C

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

The mod-

We already met two of the clusters: C_{1} is Gauss's group of euler units, and C_{m} —the cluster consisting solely of the residue 0. Those are the *only* clusters that exist in *every* residue system.

**Example Z _{12}**: The clusters for modulus

C

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

The method is inefficient because it generates each member of the cluster multiple times. Notice in the
Z_{12} example, for instance, that C_{1} has twice as many members as C_{3}: There
are not enough residues in any of the clusters except
C_{1}.

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_{1}| of residues in C_{1} is calculated
using the totient function *φ*(*m*) later named Euler's Phi function. If
*c _{r}* ≠ 1
then the size of C

Anyway, |C

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_{36}:

Units colored, Omes

The nine clusters of Z

The two prime power factors of 36 are 2

Each of the 36 residues of Z

**e.g.** 34 is in ro4

Almost as important as clusters are their "traces": The ** trace** T

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

ƒ

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

First, the power stack of clusters with centers from *c*^{1} 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_{1} 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

Example traces:

For modulus 12 the traces of the clusters are:

T_{1}={all the residues mod *m*},
T_{2}={2, ** 4**, 6, 8, 10,

The * shadow* of
a cluster contains just "the usually more",

Example shadows:

For modulus 12 the shadows of the clusters are:

S

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

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

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

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

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

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*^{2}, *u*^{3}, …

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

until the first time

which occurs if and only if

Then ω

Example: The power sequence for 16 (mod 72) is 16, 40, 64, 16 so k = 4, ω

Easily confirm by calculating

Other methods require computing the prime factorization of the modulus. It is a benefit that the above algorithm does not. ↑ to 'Deep' menu

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

Solution: ω_{16}≡64 and 64⋅56≡56 so 16 | 56.

Thus *x*≡56/16≡56⋅40≡8.

Confirm: 16⋅8≡56? yes.

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

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

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_{1},
C_{19}, C_{29}, and C_{551}.

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}=1, ω_{19}=494, ω_{29}=58,
ω_{0}=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_{19} then the congruence
to solve is

5⋅*x* ≡ 549⋅494 ≡ 114, which yields

*x*=114/5≡133.

Assuming C_{29} yields *x* ≡ 87, C_{1}
yields *x* ≡ 220, and C_{551} naturally yields *x* ≡ 0 :-)

If we multiply through by

There are some special cases where I can see how to proceed. The most obvious case is when the integer discriminant

5.

The euclidean integer discriminant *b*^{2}−4*ac*=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*^{2}+*x*+60 ≡ 0 (mod *72*),

and its *complete* list of solutions is:

*x*≡3 in C_{3}, 12 in
C_{12}, 59 in C_{1}, and 68 in C_{4}.

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.

6.

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*^{2}−4*ac*))/2*a*
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_{17}, 314 in C_{1}, 323 in C_{17},
and 518 in C_{1}. We expected 314 and 323 but where did the other two
come from?

Answer: We thoughtlessly took √81 to be simply ±9, but Z_{663} contains those along with
±264 as the *four*
square roots of 81 (mod 663) — all four are in C_{3}. They produce the unexpected extra
solutions for Example 6.
The same observation serves for Example 5 as well.

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

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.

↑ to 'Deep' menuResidue *r* is *not* a residual unit if *r*^{2} 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 *omega*s 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*_{0},
*s*_{1} ≡ *s*_{0} / *r*,
*s*_{2} ≡ *s*_{1} / *r*,
*s*_{3} ≡ *s*_{2} / *r*, …

When *r* is a residual *integer* the sequence usually *terminates*
at some *s _{k}* which

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

Otherwise, the trick to finding all "quotients" is to use euclidean integer division to remove the common factors

Since euler units divide

Since

provides the complete set of quotients modulo

The

It was also shown that the number of distinct solutions is

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

The

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 |

Calculating the "c" of the (c;e) factorization of any residue *r* is easy: *c _{r}* is simply
the greatest common divisor gcd(

The euler factor is a bit trickier. Define

{

Notice, the number of quotients to choose from is

48 ≡ 24⋅5.

48 ≡ 24⋅11.

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

**The modular "(c;e)-quotient"**

**Early version**: To divide *n* by *d* we euclidean-divide *c _{n}* by

The "early" version guarantees that

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.

The e-factor 13 of

The exponent of prime 2 in

The fact that

The result is that the

We tried moving such excess unit-factors back into

Unless a solution is discovered,

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

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

The "integer factor of

The number of distinct alternative units for

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.

48 ≡

The integer part of the unit

as is the unit part of the integer

48 ≡

48 ≡

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

The (i;u)-quotient's divisibility condition

This shows that the (i;u)-quotient

Uniqueness, just as with (c;e)-division, is achieved by re-arranging the calculation to preserve the overlap of the transparency-sets

First calculate

(i,u) division works quite like (c,e) — sometimes with different quotients — but

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 'Deep' menu

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

The forms are equivalent if β ≡

Knowing β and γ we find

There are just three issues that could get in the way of this process: First,

The residue system Z

8. *x*^{2}+*x*−12 ≡ 0 (mod 72) (Example 5 revisited)

Modular division fails at β = *b*/2 because in Z_{72} the
center *c*_{2}=2 does not euclidean-integer divide the euler center *c*_{1}=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.

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.

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

↑ to 'Deep' menu

**Integer division ambiguity ...**

... has been resolved as of May, 2022.

Examines residues from the point of view that a residue is just an infinite set of euclidean integers. Myself, I prefer to think of residues as a nearly independent category of numbers.

a Michigan company since 1978

Most recent update of this guide: July 15, 2023, 2:30pmET

Copyright © GRS Enterprises, NLC, 2010-2023

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