Keo's Notes

Modular Arithmetic

12 min read

Number-Theory

Definition

Modular arithmetic is a system of arithmetic restricted to the remainders. , , , such that , (Euclid’s Division Lemma)

Basic Properties

  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)

Fermat’s Little Theorem

Let be prime and , then

Proof 1 Using the Reduced Residue System . This gives Since , you get .

Proof 2 by Induction

  1. Base case:
  2. Induction forwards. Assume , then by assumption.
  3. Induction backwards. Assume , then . For is odd. so we get which by our assumption . For , we get which by our our assumption .
  4. Therefore we get the fact that . If has an inverse you get .

Euler’s Theorem

(Euler’s Totient Function) Euler’s Theorem is a more general case of Fermat’s Little Theorem. It states that

In the case of being prime and it simplifies to Fermat’s Little Theorem. Proof

  1. By considering the elements of (The reduced residue system ), multiplying them together. .
  2. Hence
  3. Since the products only contain coprime to the whole product will share no prime factors to and so the whole product is coprime to and therefore can be cancelled.
  4. Therefore .

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 . More generally exists if and only if . Proof

  1. 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 fact that . Proof

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

Fractional Behaviour

You can write inverses as a fraction like . They can be added and multiplied normally. Proof of Fractional Addition Proof of Fractional Multiplication

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

Wilson’s Theorem

Start with using the fact that every element in has a unique inverse, you can pair these elements up to get . Multiplying both sides by you obtain Wilson’s Theorem

Proof of the reverse direction Assume is composite then since both must be contained in so . Therefore if , can’t be composite and is therefore prime.

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 ,

  • the equation has no solutions
  • the equation has solutions in the set of least residues

Advance Properties and Results

Results

  5. For , (Wolstenholme’s Theorem). This is also equivalent to saying .

Explanations

    1. By Bezouts Theorem .
    1. We have .
    2. , with
    3. So . So
    4. Therefore
    1. Prove that
      1. Expanding LHS obtains .
      2. Since , all terms except and are divisible by
    2. Inductive proof.
      1. Base case: it is clear that satisfies the equation.
      2. Assume .
      3. , by our assumption
    1. By Fermat’s Little Theorem LHS.
    2. One of is .
  5. For , (Wolstenholme’s Theorem). This is also equivalent to saying .
    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.

Euler’s Totient Function

Euler’s totient function is defined as

Properties

  1. is Multiplicative Function
  3. Let

Explanations

  1. is Multiplicative Function
    1. Consider . Then consider the set numbers .
    2. By Euclid’s Division Lemma every such number can be written in the form with . You can think of putting this in a grid with each being in row index and column index .
    4. Let be the subset of that has coefficient for e.g. .
    5. Each forms a complete residue class as so for each there are elements coprime to .
    6. Then let be the subset of with remainder e.g.
    7. Each forms a complete residue class as so for each there are elements coprime to .
    8. So the total amount that is coprime to is - You can think this as starting in the top row there are elements that are coprime to and each of them form a column in which there are that are also coprime to . Only the columns where the first element is coprime to work as any element that has a common factor with will form a column in which all those elements share that common factor with . (This is due to the fact that )
    1. Every number other than a multiple of is coprime to . There are multiples of and there are numbers so combing them we get
  3. Let
    1. Using property 2,
    2. Since is multiplicative and primes are pairwise coprime.
  1. . (This is completely multiplicative as is - ).
    1. Let
    2. Every positive divisor .
    4. Using the fact that is multiplicate we get
    5. You can repeatedly factor out from the summation with as it is constant as you are changing all up to but not including so the summation is constant and can be factored out.
    6. This obtains
    7. For each term we get which using property 2 gets a telescoping sum of
    8. Replacing every sum we get
    1. INSERT PROOF

Modular Contradictions

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

Graph View

Backlinks