 # Relations And Proofs

## 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 {, , , . . . , [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] = , 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.

## Solution Preview

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. \$60.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.