1) Prove that you can cancel a in ab =ac (mod m) if gcd(a, m) = 1. 2) Show by e
ID: 2976073 • Letter: 1
Question
1) Prove that you can cancel a in ab =ac (mod m) if gcd(a, m) = 1. 2) Show by example that cancellation is not necessarily possible if gcd(a, m) > 1Explanation / Answer
Cancellation Law: Can cancel a in ab = ac (mod m) if gcd(a, m) = 1 Proof: If ab = ac (mod m) then m | (ab-ac) [defn of equality mod m], i.e. m | a(b-c). If gcd(a, m) = 1 then m¬|a, so m | (b-c), i.e. b=c (mod m). Note: if gcd(a, m) > 1 then we can't always cancel, e.g. 2×1=2×4 (mod 6), but can't cancel the 2's Fermat's Little Theorem: ap-1 = 1 (mod p) if p prime, gcd(a, p) = 1 Proof: If p is prime and gcd(a,p) = 1 then the numbers 1a, 2a, ... (p-1)a are distinct (mod p) since if n1a = n2a (mod p) then n1 = n2 (mod p) by the Cancellation Law. Since none of 1a, 2a, ... (p-1)a are zero (mod p) and there are only (p-1) distinct non-zero numbers (mod p), the numbers 1a, 2a, ... (p-1)a must be congruent to 1, 2, ... p-1 in some order. Multiply all these congruences together to get: a·2a·...·(p-1)a = 1·2·...·(p-1) (mod p) ap-1(p-1)! = (p-1)! (mod p) ap-1 = 1 (mod p) (since gcd((p-1)!, p) = 1 the Cancellation Law applies. Core of proof shamelessly stolen from [PS1]) a 2a (mod 5) 3a (mod 5) 4a (mod 5) 1 2 3 4 2 4 1 3 3 1 4 2 4 3 2 1 a a2 (mod 5) a3 (mod 5) a4 (mod 5) 1 1 1 1 2 4 3 1 3 4 2 1 4 1 4 1 Euler's Theorem: aphi(m) = 1 (mod m) if gcd(a, m) = 1 Euler's Theorem is a generalization of Fermat's Little Theorem and the proof presented here has the same form as the proof presented above for Fermat's Little Theorem. phi(m) denotes the number of positive integers less than m which are relatively prime to m. For prime m, phi(m) = m-1 and we have the special case of Fermat's Little Theorem. Proof: Let r1, r2, ... rphi(m) be the set of phi(m) integers less than m and relatively prime to m. If gcd(a,p) = 1 then the numbers r1a, r2a, ... rphi(m)a are distinct (mod m) since if ria = rja (mod m) then ri = rj (mod m) by the Cancellation Law. Since each ria is relatively prime to m and there are only phi(m) distinct numbers relatively prime to m, the numbers r1a, r2a, ... rphi(m)a must be congruent to r1, r2, ... rphi(m) in some order. Multiply all these congruences together to get: r1a·r2a·...·rphi(m)a = r1·r2·...·rphi(m) (mod m) aphi(m)·r1·r2·...·rphi(m) = r1·r2·...·rphi(m) (mod m) aphi(m) = 1 (mod m) (since gcd(r1·r2·...·rphi(m), m) = 1 the Cancellation Law applies) a 5a (mod 12) 7a (mod 12) 11a (mod 12) 1 5 7 11 5 1 11 7 7 11 1 5 11 7 5 1 phi(12) = 4 a a2 (mod 12) a3 (mod 12) a4 (mod 12) 1 1 1 1 5 1 5 1 7 1 7 1 11 1 11 1 Wilson's Theorem: (n-1)! = -1 (mod n) if and only if n is prime [Also known as Fermat's Christmas Theorem] Case 1: n is prime Apart from 1 and -1 which satisfy x = x-1 (mod n), all the numbers from 1 to n-1 may be grouped in pairs satisfying x = y-1 where x and y are distinct. So (n-1)! = 1·2·...·(n-1) = 1·...pairs of numbers which multiply to give 1 (mod n)...·(n-1) = 1·-1 (mod n) = -1 (mod n) Case 2: n is composite If n = 4 then (n-1)! = 6 = 2 (mod n). If n > 4 then let n = PQ for some P > 1 and Q > 1. If P ¬= Q then both P and Q occur in 1..(n-1), so n | (n-1)!, i.e. (n-1)! = 0 (mod n). If P = Q then n = P2 and both P and 2P occur in 1..(n-1), so n | (n
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.