## Transcribed Text

Things you should be able to do
1. Be able to prove a relation is an equivalence relation and be able to find
the equivalence classes.
2. Find the remainder when a
b
is divided by m (solve a
b ≡ x (mod m) with
0 ≤ x < m). Here you use Fermat’s Little Theorem or the Euler-Fermat
Theorem.
3. If [a] is a congruence class modulo m find [a]
−1
.
4. Find all solutions to a linear congruence (Linear congruence theorem) and
know when there is no solution.
5. Find all solutions to a pair of linear congruences (Chinese remainder theorem.)
6. Evaluate the Euler-phi function for any positive integer.
Things you should be able to define
1. Equivalence Relation (reflexive, symmetric, transitive) Also the equivalence class of an element and a class representative
2. Congruent modulo m (a ≡ b (mod m) if and only if m|b − a.)
3. Congruence class modulo m ([a] = {x ∈ Z | x ≡ a (mod m)}.)
4. Integers modulo m (Zm denotes the set of congruence classes
{[0], [1], [2], . . . , [m − 1]}.)
5. The definition of addition, subtraction and multiplication in Zm.
6. Inverses of congruence classes (If [a] and [b] are congruence classes then
[b] is the inverse of [a] if [a][b] = [1], in this case we write [a]
−1 = [b].)
7. Relatively prime (integers a and b are relatively prime if gcd(a, b) = 1.)
8. Euler phi function (φ(n) is the number of integers less than or equal to n
that are relatively prime to n.)
Theorems with names
You should be able to state these theorems and know their names
1. Fermat’s Little Theorem (if p is a prime then a
p−1 ≡ 1 (mod p) - also be
able to prove this using the information in the proofs list)
2. Linear Congruence Theorem (there are two parts to this, first when there
are solutions and second the list of all solutions.)
3. Chinese Remainder Theorem
4. Euler-Fermat Theorem (if a and m are relatively prime then a
φ(m) ≡ 1
(mod m))
List of Proofs
I will only omit one of these.
1. Let a, b, x, y and m be integers. Prove if a ≡ x (mod m) and b ≡ y
(mod m), then ab ≡ xy (mod m)
2. Let S = R. Define a relation R on S by xRy if x − y is an integer. Prove
that R is an equivalence relation.
3. Let R be an equivalence relation on a set S and let a, b ∈ S. Denote the
equivalence class of a by [a] and the equivalence class of b by [b]. Prove
that that [a] ∩ [b] = ∅ if and only if a and b are not related (so a Rb 6 ).
4. Prove that [a] ∈ Zm has an inverse if and only if gcd(a, m) = 1.
5. Let {b1, b2, . . . , bφ(m)} be the list of all integers between 1 and m − 1
that are relatively prime to m. Let m be an integer with gcd(m, a) = 1.
Show that no two elements of the list {ab1, ab2, . . . , abφ(m)} are congruent
modulo m.
6. Let {b1, b2, . . . , bφ(m)} be as in the previous question. Assume that the set
{ab1, ab2, . . . , abφ(m)} contains an element congruent to bi modulo m for
each i ∈ {1, . . . , φ(m)}. Using this assumption and the previous question
prove the Euler-Fermat Theorem.
7. Assume that p and q are relatively prime integers. Prove that if x is an
integer such that
x ≡ p (mod q) and x ≡ q (mod p)
then x ≡ p + q (mod pq).
8. Prove that φ(m) = m − 1 if and only if m is prime.

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.