Divisibility and Congruences

Use the division algorithm to write the following divisions as $n = dq + r$ with the variables defined in the theorem:

1. 17 is divided by 9
2. 1234 is divided by 23
3. 0 is divided by 13
4. 8 is divided by 1

Determine whether the following integers are congruent to 3 modulo 7:

1. 37
2. 66
3. -17
4. -67
5. 80

List all integers between -100 and 100 that are congruent to -1 modulo 25

Find counterexamples to the following statements:

1. If $ac \equiv bc \pmod m$ where $a, b, c, m \in \Z$ with $m \ge 2$, then $a \equiv b \pmod m$.
2. If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ where $a, b, c, m \in \Z$ with $m \ge 2$, then $a^c \equiv b^d \pmod m$.

The first part of this exercise should convince you: you cannot “divide” both sides by $c$ in modular arithmetic!