Reviewed meaning of mod and division with quotient and remainder

We discussed the meaning of mod and division. Recall, that "$a$ divided by $b$" means: \[ a = qb + r \text{, where $0 \le r \lt b$} \] The quotient and remainder are unique.

A note about evaluating expressions "mod $n$"

We went over the facts that \[ (a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n \] and \[ (a b) \mod n = ((a \mod n) (b \mod n)) \mod n. \] This means that when evaluating arithmetical expressions "mod n" we are free to reduce mod n at the very end only, or after every operation, or to sprinkle mod n's in wherever we want.

When a multiplicative inverse "mod n" exists

Suppose I have $d$ and $Z_n$ and want to know whether $d$ has a multiplicative inverse. We showed that $d$ has a multiplicative inverse if and only if $\gcd(d,n) = 1$.

The Euclidean Algorithm

We went over the Euclidean GCD Algorithm (see Unit notes). This is very important for all sorts of reasons, but in the "multiplicative inverse" discussion, it was important because it allowed us to determine when a number has an inverse.