Find the unique q and r guaranteed by the division algorithm…
Division “algorithm”: For all a, b with b > 0 there exist unique
integers q, r such that a = bq + r and 0 ≤ r < b
a = 23, b = 4
q = 5, r = 3
a = 139, b = 100
q = 1, r = 39 (with b a power of 10, q and r pick out digits)
a = 110, b = 139
q = 0, r = 110 (a can be less than b)
a = 36, b = 3
q = 12, r = 0
a = -9, b = 6
q = -2, r = 3
Prove that for all integers a and natural numbers n, -a ≡ (n-a) (mod n)
x ≡ y (mod n) means n | (x-y) which means x-y = kn for integer k
-a - (n-a) = -n = -1 × n implies n | -n so -a ≡ (n-a) (mod n)
This is the basis for how lots of mechanical and electronic calculators, including
computers, handle negative numbers
x is actually treated as the r from x = 100…000 q + r (for a device
working in base 10, computers do the equivalent in base 2)
a = bq + r iff a ≡ r (mod b)
Prove that for all integers a, b, c, and d, and all natural numbers n, if
a ≡ b (mod n) and c ≡ d (mod n), then a+c ≡ (b+d) (mod n)
(Progress check 3.29)