The study of a notion, viz. that of residue classes

The study of a notion, viz. that of residue classes

The working mathematician introduces new concepts as he goes along, and he sometimes introduces new notations in connection with them. I think that each time he does so he should ask himself questions such as "Is this concept worth being introduced?" or "Do I really need this new notation?" Even if it cannot give the complete conclusive answers, a course on Mathematical Methodology should raise and discuss such questions. In this note we conduct a case study -knowing full well the limitations of such an approach- and have chosen the topic of residue classes.

Remark This choice is largely accidental. Some time ago - EWD770- I seemed to be able to make good use of the concept, but being only faintly familiar with it, I needed to build up what theory I needed about it. While doing so I made a mental note that this might be a good candidate for such a "conceptual case study": it starts from a very modest mathematical base, it raises notational questions, and quickly leads to not entirely trivial results. To avoid any misunderstanding, the following development is not a historical reconstruction: in writing it I did not consult the literature. Also I would like to make it clear that I have very little interest in number theory per se. (End of Remark.)

For integers $q$ and $x$ we can raise for $q \neq 0$ the question whether $q$ divides $x$ . (If $q = 0$ , we can raise the question too, but then the answer is less clear; we skirt that issue.) Since divisibility by $-q$ is the same as divisibility by $q$ , if it is no loss to confine our selves to positive $q$ if that comes in handy, and we shall do so. (In a moment we shall see that a constraint to natural $x$ does not come in handy.)

Number theory being what it is, we may ex- pect the divisibility by $g$ to be most inter- esting for some $g$ that is prime. Should we immediately restrict our attention to prime dividers?

In our current explorative state the answer is "No" because divisibility by $q$ is perfectly defined for non-prime $q$ , and we can always decide later: at this stage we should keep our options open. (Note that I am not advocating "generality" for its own sake: if all interesting results are confined to $q$ 's that are prime and considering $q$ 's that are not prime only leads to ugly complications, we should restrict ourselves in the final presentation right from the start to prime dividers.)

For the boolean expression " $g$ divides $x$ " exists -since when? I have no idea- a more

or less accepted formal notation, viz.

$$ q | x $$

(I say "more or less" because, though I have encountered it regularly in the literature, I do not remember a single author - myself included- being very explicit about its syntactic status. Do we admit qI $x + y$ for qI $(x + y)$ and qIx v qly for (qIx) v (qIy)? In this text I propose we do.)

What do we know about our relation I ? Well, a lot. Because

$$ x \mid y \equiv x = x \mathrm {g c d} y $$

we know -see EWD954 - :

because, gcd is idempotent, $l$ is reflexive:

X

because gcd is associative, is transitive:

$\because x \mid y \land y \mid z \Rightarrow x \mid z\therefore$

because gcd is symmetric, 1 is anti-reflexive:

$x \mid y \land y \mid x \Rightarrow x = y$

because is a left-hand zero-element of gcd, it is a left-hand extreme of $\mid$ :

${11y}$

because 0 is a right-hand unit-element of gcd, it is a right-hand extreme of 1 :

Well, that is very encouraging; it makes obvious

that our relation "divides" might be something worth pondering about. Let us look what it does with arithmetic operations and let us take the additive ones first. We have

$\left. \begin{array}{l} 9 \times 9 \Rightarrow 9 \times y \ \end{array}\right} {10}$ and then as consequences of all the above $\Rightarrow \;q\left| x\right. \equiv q\left| {-x}\right.$ and $\therefore q \mid x \land q \mid y \Rightarrow q \mid x + y\;,\;$ and in particular $\left| {x - {2x}}\right| = \left| {{r}{1}^{2} + {r}{2}^{2} - {r}{1}{r}{2}}\right| < \left| {x - {2x}}\right|$ $\left| {x - y}\right| = \left| {y - x}\right|$ $\Rightarrow q \mid {x}^{2} - 2$ ,即 ${x}^{2} - {2x} + 1 \neq 0$

i.e. now viewed as relation between $x$ and $y$ - "For fixed $q$ " so to speak - $q \mid x - y$ is reflexive, symmetric, and transitive, i.e. $q \mid x - y$ is what is known as an equivalence relation.

What about multiplication? Well, $q \mid x \Rightarrow q \mid x \cdot y$ is about the only thing I can think of. But if

gives u.s.

$$ \begin{array}{l} q | x - x ^ {\prime} \land q | y - y ^ {\prime} \ \Rightarrow q | (x - x ^ {\prime}) \cdot y \land q | x ^ {\prime} \cdot (y - y ^ {\prime}) \ \Rightarrow q | (x - x ^ {\prime}) \cdot y + x ^ {\prime} \cdot (y - y ^ {\prime}) \ = q | x \cdot y - x ^ {i} \cdot y ^ {j}, i. e. \ \end{array} $$

$\left| {x - {x}^{\prime }}\right| \land \left| {y - {y}^{\prime }}\right| \Rightarrow \left| {x \cdot y - {x}^{\prime } \cdot {y}^{\prime }}\right|$

Similarly we have - proof omitted

$\left( {x - {x}^{\prime }}\right) \wedge \left( {{y}^{\prime } - {y}^{\prime }}\right) \Rightarrow \left( {{x}^{\prime } + {y}^{\prime }}\right) - \left( {{x}^{\prime } + {y}^{\prime }}\right) = 0$

Now all this is notationally unattractive. Evidently, the assertion $q \mid x - y$ is an interesting assertion about $x$ and $y$ , but as written down it fails to express in a familiar manner its symmetry and a few other properties it shares with equality. One of the notations for $q \mid x - y$ that came in use is

$$ x \equiv y (\mod q) $$

• read as " x congruent y modulo 9" -, in which "≡" figures as a somewhat weakened equality with the suffix "(mod q)" pinning that weakening down. I have two reasons to depart immediately from this notation: the personal one that I have decided to adopt "≡" for the associative equality between boolean arguments -in which role I shall need it in a moment- and the general one that there is little to be said in favour of a half-infix and half-postfix operator. For the purpose of this discussion I shall denote the symmetric relation $q|x-y$ with an infix conq:

$$ x \equiv 9 \mathrm {y} $$

In this notation we can summarize

$$ \begin{array}{l} x \underline {{\mathrm {c o n} . q}} x \ x \underline {{\underline {{\operatorname {c o n}}}}} 9 y \equiv y \underline {{\underline {{\operatorname {c o n}}}}} 9 x \ x \underline {{\mathrm {c o n}}} q y \wedge y \underline {{\mathrm {c o n}}} q z \Rightarrow x \underline {{\mathrm {c o n}}} q z \ x \underline {{\underline {{\mathrm {c o n}}}}} q x ^ {\prime} \wedge y \underline {{\underline {{\mathrm {c o n}}}}} q y ^ {\prime} \Rightarrow x + y \underline {{\underline {{\mathrm {c o n}}}}} q x ^ {\prime} + y ^ {\prime} \ x \underline {{\underline {{\operatorname {c o n}}}}} 9 x ^ {\prime} \wedge y \underline {{\underline {{\operatorname {c o n}}}}} 9 y ^ {\prime} \Rightarrow x \cdot y \underline {{\underline {{\operatorname {c o n}}}}} 9 x ^ {\prime} y ^ {\prime}, \ \end{array} $$

a bunch of properties of conq that are shared by equality. Treating "being congruent" as "being equal, but not fully" is not very satisfactory, and we can do something about it in a few steps.

The first thing to do is to use a metaphor - "adopt a jargon" or "introduce a nomenclature" - that does justice to the fact that "being congruent" is -see the first three summarized properties - an equivalence relation and, hence, induces a partitioning of the domain -integers so far - that we have been talking about. We can do so by giving the partitions a generic name , and the one that has been introduced and generally accepted is "residue classes". It enables us to replace the expression "being congruent" by "belonging to the same residue class". It allows us to rephrase the last two summarized formulae as "the residue class to which a sum (product) belongs is determined by the residue classes to which the addenda (Factors) belong".

Before continuing our linguistic and notational let us determine the number of residue classes.

from

$$ (\underline {{A}} x, y: 0 < x < y < q: \neg q | x - y) $$

we deduce that there are at least $g$ residue classes. From the fact that for each $y$ the

equation

$$ x: (0 \leq x < q \land q | x - y) i s s o l v a b l e, $$

we conclude that there are at most $q$ residue classes. Summarizing: there are precisely $q$ residue classes, and the last equation puts them into one-to-one correspondence with the values $x$ from the range $0 \leq x < q$ .

More precisely, that equation having precisely one solution, it defines that solution as a function of $y$ and $q$ , the free parameters in the body of the equation. For that function a special notation has found its way in the literature, viz. an infix mod :

$$ x = y \mod q \equiv 0 \leq x < q \land q | x - y $$

Because

$$ q \mid x - y \equiv x \mod q = y \mod q, $$

we can now express "being congruent modulo $q$ " - or, equivalently, "belonging to the same residue class (modulo $q$ )" - in terms of an equality, viz. yielding the same values under application of the (postfix) operator "mod $q$ ".

Remark The very attentive reader will have noticed that, rather implicitly, we did something else: we derived from the binary operator "mod" the unary operator "mod q". More than a century after the discovery of residue classes, this device would become known as "Currying". (End of

Remark.)

We have done more: the postfix operator "mod q" assigns to each integer a value that is characteristic for the residue class to which the integer belongs, and we should observe that this is a general way of characterizing partitionings of any domain: choose a function that assigns the same value to elements in the same partition and different values to elements in different partitions.

what does it do to our five propositions we listed in terms of con.g? The first three yield:

X mod q = X mod q , which is not very interesting ; $x \bmod q = y \bmod q \equiv y \bmod q = x \bmod q,$ which is no more than the symmetry of the equality; $x \bmod 9 = y \bmod 9$ $\wedge y\bmod q = z\bmod q \Rightarrow$ $x\bmod q = z\bmod q,$ which boils down to the transitivity of equality.

The last two propositions become more interesting if we choose $x' = x \mod q$ and $y' = y' \mod q$ and realize that $(x \mod q) \mod q = x \mod q$ . The antecedents are then true, and we get the almost nice consequences

$$ (x + y) \mod q = ((x \mod q) + (y \mod q)) \mod q $$

$$ (x \cdot y) \mod q = ((x \mod q) \cdot (y \mod q)) \mod q $$

Almost nice. Had it not been for the final

The problem with the integer $\rightarrow$ integer operator mod $q$ is that it characterizes each residue class by one of its members, and - somewhat arbitrarily - we have chosen its one and only member $x$ satisfying $0 \leq x < q$ . (Hence the need for that additional "mod $q$ " at the far right: its argument could be "out of range".)

The way out of this dilemma is to remove the observed arbitrariness by replacing "mod $g$ " as characteristic function of the partitioning by one of type integer $\rightarrow$ residue class. No longer bothering to mention $g$ explicitly -consider it as a global parameter- we denote it by a pair of braces. Being a characteristic function for the partitioning induced by the equivalence relation $g|x-y$ it satisfies

$$ 9 \vert x - y \equiv {x } = {y } $$

In the preceding paragraph we made really two steps -jumps, if you like-. Besides the new function type integer $\rightarrow$ residue class we introduced "residue class" as a (q-valued)

type in its own right! So far, our only benefit is that the "normal" equality is defined on it, and that is already something: it allows us, for instance, to formulate now the theorem

$$ {x + q } = {x } $$

In view of the above it stands to reason to define for our new type addition, subtraction, and multiplication by

$$ \begin{array}{l} {x } + {y } = {x + y } \ {x } - {y } = {x - y } \ {x } \cdot {y } = {x \cdot y } \ \end{array} $$

thus seeing to it that ${3}$ nicely distributes over the arithmetic operators considered so far.

Remark We have "overloaded" + , -, and ., since at the right-hand side their operands are integers, at the left-hand side their operands are residue classes. We should not be frightened by this: firstly, the overloading is necessary if we wish to see the above three formula as distribution laws, secondly we should be quite used to it, when we interpret

$$ a \cdot (b + c) = a \cdot b + a \cdot c $$

as the distribution of the scalar product over the vector sum : the + at the right-hand side adds reals. (End of Remark).

Have we achieved something? Well, we have introduced for residue classes a (symmetric) multiplication that distributes over the (symmetric) addition:

$$ \begin{array}{l} {x } \cdot ({y } + {z }) \ = \begin{array}{l} {{\mathrm {d e f i n i t i o n o p + f o r r e s i d u e c l a s s e s} }} \ {{x }: {y + z }} \end{array} \ = \begin{array}{l} {{\mathrm {d e f i n i t i o n o f} \cdot \mathrm {f o r r e s i d u e e l a s s e s} }} \ {{x \cdot (y + z) }} \end{array} \ = \begin{array}{l} {\left{\mathrm {d i s t r i b u t i o n o f a r i t h m e t i c \cdot o v e r a r i t h m e t i c} + 3 \right.} \ {\left{x \cdot y + x \cdot z \right}} \end{array} \ = \begin{array}{l} {{\mathrm {d e f i n i t i o n o f} + \mathrm {f o r r e s i d u e c l a s s e s} }} \ {{x \cdot y } + {x \cdot z }} \end{array} \ = {\mathrm {d e f i n i t i o n o p} \cdot \mathrm {f o r r e s i d u e c l a s s e s , t w i c e} } {x } \cdot {y } + {x } \cdot {y } \ \end{array} $$

Encouraging, though from another point not impressive: one could conclude that the arithmetic with residue classes is so similar to that with integers that you don't really need very much to distinguish between them and that you don't really need to bother about the braces at all. But let's keep them.

whereas, without the addition of residue classes, the equation in the integer $x$

$$ x: ({x + y } = {z }) $$

has no unique solution, the one in the residue class ${x}$ ${x} : \left( {{ x + y} = { z} }\right)$

has a unique solution, viz. ${2 - y}$

Is this important? Yes, I think so, for it invites us to look at equations like

$$ x: ({x \cdot y } = {z }) \quad , \qquad a n d $$

$$ {x }: ({x \cdot y } = {z }) $$

Let us look at the first one, which we may rewrite as

$x : \left( {9 \mid x,y - z}\right)$ ,from which we conclude that it may have no solutions at all - e.g. For $9,y,z = 6,2,3 -$ or may have solutions less than apart -e.g. for $9,y,z = 6,2,4 -$ .

When has the second equation a unique solution (if it has one)? From

$$ {x \cdot y } = {z } \land {x ^ {\prime} \cdot y } = {z } $$

we would like to conclude ${ x} = { {x}^{\prime }}$

$$ \begin{array}{l} \mathrm {N o t e} \quad {x } = {y } \ = {\mathrm {a r i t h m e h c} } \ {x } = {y + o } \ = {\mathrm {+ f o r r e s i d u e c l a s s e s} } \ {x } = {y } + {0 } \ = {\mathrm {a r i t h m e t i c} } \ {x } - {y } = {0 } \ = {\text {- p r e s i d u e c l a s s e s} } \ {x - y } = {0 } \ \end{array} $$

(End of Note)

We can conclude

$$ {(x - x ^ {\prime}) \cdot y } = {0 } $$

but that does not suffice, e.g. $9,{x},{x}^{\prime },y = 6,2,4,3$ . The question of uniqueness raises the question under which circumstances we have -the usual!

$$ {x \cdot y } = {0 } \Rightarrow {x } = {0 } \vee {y } = {0 } $$

This implication does not hold if $q$ is composite! With $q = 6$ , for instance, for $x, y = 2, 3$ , the antecedent is true, whereas the consequent is not. So, for composite $q$ we get a theory in which a product can be zero without any of its factors being zero. Surely something worth investigating, but we won't do so here and will from now on restrict ourselves to values of $q$ equal to some prime $p$ , under which constraint the above implication holds.

Consequently, for ${y} \neq {0}$ and ${x}$ ranging over the $p$ residue classes, the values ${x,y}$ are all distinct , i.e. also range over the $p$ residue classes. Consequently, for ${y} \neq {0}$

$$ {x }: ({x \cdot y } = {z }) $$

has a unique solution, which we may denote by ${z} / {y}$ , thus introducing a quotient of residue classes, provided the "denominator" differs from ${0}$ .

Remember that we had introduced for residue classes an addition and a multiplication satisfying

$$ {x } + {y } = {x + y } $$

$$ {x } \cdot {y } = {x \cdot y } $$

Is there a sense in which our newly introduced quotient for residue classes can satisfy the

$$ {x } / {y } = {x / y } \quad \mathrm {f o r} {y } \neq {0 }? $$

In other words, may the braces distribute over division as well?

The answer is "no" unless we are willing to extend the braces from a function formerly only defined on integers to a function defined on rationals. The answer is "yes" if we do extend the function to rationals whose denominator $y$ satisfies ${y} \neq {0}$ . The reason is that ${x} / {y}$ - defined as unique solution of a linear equation - indeed only depends on the (normal) value of the fraction $x / y$ , more precisely:

$$ {w } \neq {0 } \land {y } \neq {0 } \Rightarrow {x } / {y } = {w \cdot x } / {w \cdot y } $$

To demonstrate this we observe that for any $w, x, y,$ and $z$

$$ \begin{array}{l} {z \cdot w \cdot y } = {w \cdot x } \ = {\mathrm {r e s i d u e a r i t h m e t i c} } \ {2 \cdot w \cdot y - w \cdot x } = {0 } \ = {\mathrm {a r i t h m e t i c} } \ {w \cdot (2 \cdot y - x) } = {0 } \ \end{array} $$

$$ \begin{array}{l} = {p \text {i s p r i m e} } \ {w } = {0 } v {2 \cdot y - x } = {0 } \ = {{w } \neq {0 } } \ {2 \cdot y - x } = {0 } \ = {\mathrm {r e s i d u e a r i t h m e t i c} } \ {z \cdot y } = {x } \ \end{array} $$

i.e. the same $z$ solves the equations for ${x} /{y}$ and for ${w.x} /{w.y}$ respectively.

Since all properties of rational arithmetic (such as $a / (b / c) = (a \cdot c) / b$ , $a / b + c / d = (a \cdot d + b \cdot c) / (b \cdot d)$ , etc.) can be derived by defining $a / b$ as the unique solution of

$$ x: (a = b \cdot x) $$

all these properties carry over to the rational arithmetic of residue classes, the only difference being that the null-element differs: in the normal case the numerator should differ from 0 , in the residue arithmetic it should differ from ${0}$ . In both cases the requirement guarantees the existence of a unique solution.

And now we can start building up a theory, coming up with theorems such as

$\left{ {x}^{3}\right. = \left{ {y}^{3}\right. \equiv \left{ x\right} = \left{ y\right} \vee \left{ x\right} = - \left{ y\right}$ for $p = 2\cdot n + 1$ the p residue classes consist of n non-squares and n+1 squares, being ${i^2}$ with $0\leq i\leq n$ $\left{ {\left( {\underline{\sum }\mathrm{i} : 1 \leq \mathrm{i} \leq \mathrm{n} : {\mathrm{i}}^{2}}\right) }\right} = \left{ {\left( {\underline{\sum }\mathrm{i} : 1 \leq \mathrm{i} \leq \mathrm{n} : {\mathrm{i}}^{-2}}\right) }\right}$ ,etc.

which, for instance, provides a way of demonstrating that for $p \geq 5$

$$ (\underline {{S}} i: 1 \leq i < p: (p - 1)! / i) \mod p ^ {2} = 0 $$

(This is not the place to show that demonstration, which uses the last bullet. It is mentioned as example of how extending the "brace function" to rational arguments gives our vocabulary an enrichment without which some arguments would be extremely hard to conduct.)

What did I learn? One trivial thing: square brackets are more convenient to write than braces. (Earlier I used square brackets; in this note I replaced them by braces and, at least in my hand, that was not an improvement.)

We encountered the very general technique of characterizing a partitioning of a domain by a function on that domain: belonging to the same partition equivales yielding the same function value.

More important was the discovery that for the range of that function we could introduce a type - residue class in this case. for which we could define $+$ and $\cdot$ in such a way that the func- tion distributed over these arithmetic operators. I think that the possibility of that distribution was a very encouraging indication that we were heading for something worthwhile. After all, we would like

to manipulate, and in order to be able to do so one needs laws.

Encouraging as that may be, the possibility of manipulation is not enough: the manipulations could be nothing more than insipid rewritings back and forth between different notations. The possibility of extending the domain to rationals was, I think, the crucial test. (It immediately suggest an extension to the complex plane; this is left as an exercise to the reader.)

Finally I think it worth noticing that we only got off the ground after abolishing the notation $x \equiv y\left( {\;\operatorname{mod}\;9}\right)$ ,which is ugly anyhow.

Closing remark This EWD took a very long time to complete and I am not fully pleased with its completion. I have the uneasy feeling that the exercise has taught me more than I can formulae late now. (End of Closing Remark.)

Austin, 6 January 1987

prof. dr. Edsger W. Dyrkstra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712-1188

United States of America