Recall: Induction
Let $S(n)$ be a statement about integers $n \in \mathbb{N}$. Suppose $S(n_0)$ is true for some $n_0 \in \mathbb{N}$, and that for all integers $k \ge n_0$, $S(k) \implies S(k+1)$. Then $S(n)$ is true for all $n \ge n_0$.
Every number $10^{n+1} + 3\cdot 10^{n} + 5$ is divisible by $9$, for all $n \in \mathbb{N}$.
Base case ($n = 1$):
$$10^2 + 3\cdot 10 + 5 = 135 = 15 \cdot 9. \checkmark$$Inductive step. Suppose the statement holds for $n = n_0$. Then
$$ \begin{aligned} 10^{(n_0+1)+1} + 3\cdot 10^{n_0+1} + 5 &= 10^{n_0+2} + 3\cdot 10^{n_0}\cdot 10 + (50 - 45) \\ &= 10\left(10^{n_0+1} + 3\cdot 10^{n_0} + 5\right) - 45. \end{aligned} $$The bracketed term is divisible by $9$ by assumption, and so is $45$, so the whole expression is divisible by $9$.
The Division Algorithm
Let $a, b \in \mathbb{Z}$ with $b \gt 0$. Then there exist unique $q, r \in \mathbb{Z}$ such that $$a = bq + r \quad \text{with} \quad 0 \le r \lt b.$$
Why?
Construct the set
$$S = \{\, a - bk \mid k \in \mathbb{Z},\ a - bk \ge 0 \,\}.$$If $0 \in S$, we are done, since then $b \mid a$ (take $r = 0$). If not, we will show $S \neq \emptyset$. Then by the well-ordering principle, $S$ has a least element.
Case $a \ge 0$. Then $a = a - b\cdot 0 \in S$. ✓
Case $a \lt 0$. Then $a - 2a(b) = a(1 - 2b) \in S$. ✓ (Both $a$ and $1 - 2b$ are negative, so the product is positive.)
So pick the (unique) $q$ for which the least element of $S$ is attained, and define $r = a - bq$.
Why is $r \lt b$?
Suppose not, so $r \ge b$. Then
$$a - b(q+1) = a - bq - b = r - b \ge 0,$$so $a - b(q+1) \in S$ and is smaller than $r$. This contradicts the minimality of $r$ (that is, our choice of $q$).
We show uniqueness. Suppose not. Then there are two different pairs with $$a = bq + r \qquad \text{and} \qquad a = bq' + r'.$$
Setting these equal, $bq + r = bq' + r'$, so
$$b(q - q') = r' - r \implies b \mid r' - r \implies r' - r = 0,$$since $|r' - r| \lt b$. Then $r = r'$, and so $q = q'$ as well, a contradiction. $\blacksquare$
Problems
Solve $3x \equiv 2 \pmod 7$.
Step 1. Find a multiplicative inverse of $3$ modulo $7$. List some multiples of $3$:
| $k$ | $-3$ | $-2$ | $-1$ | $0$ | $1$ | $2$ | $3$ |
|---|---|---|---|---|---|---|---|
| $3k$ | $-9$ | $-6$ | $-3$ | $0$ | $3$ | $6$ | $9$ |
We see $3\cdot(-2) = -6 \equiv 1 \pmod 7$, so the inverse of $3$ is $-2 \equiv 5 \pmod 7$.
Step 2. Multiply across by the inverse:
$$5 \cdot 3x \equiv 5 \cdot 2 \pmod 7,$$ $$x \equiv 10 \pmod 7,$$ $$x \equiv 3 \pmod 7.$$Check: $3 \cdot 3 = 9 \equiv 2 \pmod 7$. ✓
Does the table below form a group?
| $\circ$ | $a$ | $b$ | $c$ | $d$ |
|---|---|---|---|---|
| $a$ | $a$ | $c$ | $d$ | $a$ |
| $b$ | $b$ | $b$ | $c$ | $d$ |
| $c$ | $c$ | $d$ | $a$ | $b$ |
| $d$ | $d$ | $a$ | $b$ | $c$ |
Answer
No. What's the identity?
Write out the Cayley table for the symmetries of a triangle, $$D_3 = \{1,\ r,\ r^2,\ s,\ sr,\ sr^2\}.$$