Modular Arithmetic

Definition

Modular arithmetic is a system of arithmetic restricted to the remainders. Defined as

or equivalently using Euclid’s Division Lemma

Basic Properties

Theorem

5. Let and , with and

---

Reduced Residue System

Prime Reduced Residue System

Let where is prime. Then . Proof

1. Since , .
2. To prove that no 2 elements in are equal assume but .
3. Therefore .
4. Meaning you could write .

Since , you can remove as it maps to itself from to so you can remove from both sets to obtain a more useful set The Reduced Residue System .

Full Definition

The full definition of a reduced residue system is the set of integers less than , coprime to and distinct . So . However if is composite as is not guaranteed to be coprime to with as with being composite, some will divide so . and are always guaranteed to be in the set as .

The construction is the exact same as with prime modulo. Euler’s Totient Function

---

Inverses

Definition

Using the Reduced Residue System we can see that with , . In particular if we get . This means that and are multiplicative inverses . (This comes from the fact that across the real numbers You can find by using Bezout’s Identity The existence allows division.

Existence

However inverses are NOT guaranteed to exist but they are if . Theorem exists if and only if .

Proof: Let , then

Uniqueness

Inverses are unique meaning only one solution exists to (meaning an element only has one inverse). It follows that no two elements have the same inverse due to the following.

Theorem .

Proof: Assume that there are two inverses such that . So we get that . Since this must mean that but since , .

Other Useful Properties

Theorem - Pairs of Inverses Since , inverses can be written in pairs . An element can be self inverse meaning . This means (This is the only case where is self inverse).

Theorem

Proof: By definition . Let so as well as . Putting them together we get hence .

Fractional Behaviour

You can write inverses as a fraction like .

Theorem They can be added and multiplied normally.

Proof: Addition

Proof: Multiplication

Theorem

Proof: but since an inverse can never be zero as , We also can’t have both be proper divisors of (For example something like ) as . So we must have .

---

Congruence Equations

Equations with modular arithmetic are given in terms called congruence equations and their answers are usually given in terms of least residues. The set of least residues is

Since a solution represents an infinite number of solutions, you can write a general solution as:

Congruence Equation Properties

Let , Theorem

1. the equation has no solutions
2. the equation has solutions in the set of least residues

---

Modular Contradictions

In many problems you can use the fact that certain powers of can only take on certain values so if you can show that it takes on a value which is impossible you can get a contradiction Theorem

7. , by Fermat’s Little Theorem
8. , by Euler’s Theorem

---

Advance Properties and Results

Theorem

Proof: By Bezout’s Identity .

Theorem

Proof: We have . , with . So . So . Therefore .

Theorem

Proof: First we will prove that Expanding LHS obtains . Since (Shown in Divisibility), all terms except and are divisible by .

Inductive proof Base case: it is clear that satisfies the equation. Then assume . , by our assumption which then by our first claim .

Theorem .

Proof: By Fermat’s Little Theorem LHS. And one of is .

Theorem - Wolstenholme’s Theorem For , .

Proof:

2. Since we have a factor of it is now sufficient to show that for the original sum to be .
3. Since we can replace the denominators with and we can multiply the sum by to restore the amount of terms back to , the reason being that after the terms descend back symmetrically so term is equivalent to term as
4. So we get .
5. Since inverses are unique we get that so each term corresponds to a unique residue. Therefore . Since
6. Going back to step 4 we now get but which by step 2 is sufficient to prove the statement.

Theorem

Proof: