Modular arithmetic.

Although Euler was not the first to consider residue arithmetic he certainly used it to the absolute maximum. We define the residue classes:
MATH
means $a=m\cdot d+r$; $r$ is called the residue of a modulo $d$.

The idea is this: for a given number $d$ we can subdivide all numbers into $d$ categories according as their remainders upon division by $d.$ There is an entire mathematical subject of the arithemetic of residues, and in this short journey into modular arithmetic, we will consider the ancient process of "casting out nines." But first things first. Let step back and look at just plain old divibility.

Divisibility

A positive or negative integer $q$ is said to be divisible by an integer $p\neq 0$ if there is an integer $m$ such that
MATH
If this is the case we save $p$ divides $q$ and we write $p\mid q~.$ If this is not the case we write $p$ $\nmid q.$ Alternatively, if $p$ divides $q$ we also say that $q$ is a multiple of $p.$ There are many useful facts about divisibility.

  1. MATH and $p\mid p.$ Also $p\mid 1$ if and only if $p=\pm 1$

  2. If $p\mid q$ and $r\mid s$ then $pr\mid qs.$

  3. If $p\mid q$ and $q\mid r$ then $p\mid r$ .

  4. If $p\mid q$ and $q\mid p$ then $p=\pm q.$

  5. If $p\mid q$ then MATH

  6. If $p\mid q$ and $p\mid r$ $\ $then MATH for all integers $x$ and $y.$

You can test you skills by proving these facts.

Residues

Given any two non negative integers $p$ and $q$, we know that we can write
MATH
where $m$ and $r<q$ are non negative integers. (This is called the division algorithm.) Written otherwise we have
MATH
Thus we call $m$ the quotient of $\ p$ divided by $q$ and $r$ the remainder. However, the term for remainder we use here is residue. It is this quantity that we are most interested in. Indeed, we write
MATH
We read this relation as:
MATH

Using residues we may safely re-classify even and odd numbers thusly: Even numbers equal zero modulo two and odd numbers equal one modulo two. That is,
MATH
It is best to become accustom to this notation. It is convenience and precise. We can speak of the residue class of a number $q$ to be all those numbers having the same residue modulo $q.$

Many, many interesting results in mathematics and its application are concerned with the determination of which numbers are residues of other numbers.

For example, much of both ancient and modern encryption theory is based on the theory of residues.

The number 3.

The residues of the number three are $0,\ 1,\ $ and $2.$ That is to say that any number $p$ can be written as
MATH

Let's tabulate all the integers up to 44 according to its residue class modulo 3.


hint__64.png

A brief examination of the residue class of zero mod 3 reveals that each of these numbers has digits with sum also a multiple of three. Indeed we have,

Theorem

A number is divisible by three if and only if the sum of its digits 0 is divisible by three.

The proof of this result will have to wait until we've proved some interesting results about residues.

Laws of Residues

Theorem

(First law of residues) Given an integer $q$ the residue ($\func{mod}\ q$) of the sum of any two numbers is equal to the sum of the residues of the individual numbers, with the proviso that if the sum of the individual residues sum to $q$ or more, we take the residue of this value. That is, for the given integers $\ a$ and $b$,
MATH

Proof. We have $a=m_{a}q+r_{a},$ where $r_{a}<q$ and $b=m_{b}q+r_{b}$ where $r_{b}<q$. Thus
MATH

$\vspace{1pt}$We have that $0\leq $ MATH If $r_{a}+r_{b}\geq q,$ we have $r_{a}+r_{b}=q+r.$ Thus MATH Otherwise, MATH $r_{a}+r_{b}.$

Theorem

(Second law of residues) Given an integer $q$ the residue ($\func{mod}\ q$) of the product of any two numbers is equal to the product of the residues of the individual numbers, with the proviso that if the product of the individual residues product to $q$ or more, we take the residue of this value. That is, or the given integers $\ a$ and $b$,
MATH

Proof. (See problems.)

The number 9 --- casting out nines

Let us consider the residue classes for the value $q=9.$Our next law of residues applies particularly to this number$.$ First examine the chart of the residue classes for division by 9. As is obvious there are nine columns, one for each possible residue.


hint__92.png

Theorem

(Third law of residues) The residue of any number modulo 9 is equal to the residue of the sum of its digits (modulo 9).

Proof. (See problems.)




With respect to the residue 0, this theorem is sometimes called casting out nines. It gives a particularly simple and quick way to determine if a number is divisible by nine: A number is divisible by nine if the sum of its digits is also divisible by nine.




Hint for Problem 7

Some of you have a little difficulty with this problem. While the discussion below is not the full solution, the hint should get you going.

7. Let MATH be the sum of the reciprocals of all numbers with primes factors 2, 3, and 5. Prove Euler's formula in the special case, that
MATH
HINT. Usually when having a difficult time solving a problem because I don't understand where to begin. I make the problem simpler. Let's skip the multiples of $3$ and $5$ and suppose we have only multiples of $2.$ Then
MATH
and the product reduces to MATH, which you can easily expand as a geometric series
MATH
This you will note is exactly $s_{1}.$

So, what we've done here is show Euler's formula reduces to a very simple case when there is just one prime number. You could also verify the formula in the case of any single prime $p$ by the same argument.

This is the hint. Expand each of the terms MATH for $p\in \{2,3,5\}$ as a geometric series and then multiply them all together. Don't actually do the multiplication! Rather you should argue that the product of the three infinite series contains all unital fractions with denominators having only factors 2, 3, and 5.




We also fixed up a little typo.

This document created by Scientific WorkPlace 4.1.