Section 3 - Modular Arithmetic

Question 1

Congruence

Answer 1

If a, b ∈ Z, we say a is congruent to b mod n if n|a-b. We write a ≡ b mod n

Question 2

a ≡ a’ mod n and b ≡ b’ mod n

Answer 2

a + b ≡ a’ + b’ mod n and ab ≡ a’b’ mod n

Question 3

Inverse

Answer 3

If n > 0, and a is coprime to n, then a b∈Z such that ba ≡ 1 mod n is called an inverse of a mod n

Question 4

Proposition: Let n be a positive integer and x,y∈Z

Answer 4

(i) If a∈Z>=1, then ax ≡ ay mod an iff x ≡ y mod n
(ii) If a∈Z coprime to n, then ax ≡ ay mod n iff x ≡ y mod n

Question 5

Chinese Remainder Theorem

Answer 5

Let m,n be coprime positive integers (1 = sm + tn for some s,t∈)Z), a,b be any integers. Then the solution to the simultaneous congruences: x ≡ a mod m and x ≡ b mod n is:
x ≡ atn + bsm mod mn