Say which of the following are true, or false, or neither. Explain.

\begin{align*}
6|3 \amp \amp 3|6 \amp \amp 6/3 \\
\amp 8\equiv 2\pmod{3}
\amp \amp 7\equiv 2 \pmod{3}
\end{align*}

The set

\begin{equation*}
\Z=\{ \ldots,-3,-2,-1,0,1,2,3,\ldots \}
\end{equation*}

of all the whole numbers is called the integers. We say that an integer \(a\) divides an integer \(b\text{,}\) written \(a|b\) , if \(b=ak\) for some integer \(k\text{.}\) If \(a|b\text{,}\) we say that \(b\) is divisible by \(a\text{,}\) and we say \(a\) is a divisor of \(b\text{.}\) We write \(a\nmid b\) to indicate that \(a\) does not divide \(b\text{.}\) Given a positive integer \(m\text{,}\) we say integers \(a,b\) are equivalent modulo \(m\), written \(a\equiv b \pmod{m}\) , if \(m|(a-b)\text{.}\) An integer \(p>1\) whose only positive divisors are \(1\) and \(p\) is called prime.

Say which of the following are true, or false, or neither. Explain.

\begin{align*}
6|3 \amp \amp 3|6 \amp \amp 6/3 \\
\amp 8\equiv 2\pmod{3}
\amp \amp 7\equiv 2 \pmod{3}
\end{align*}

Here are two important facts about divisibility and primes.

Let \(m\) be a positive integer. For every integer \(n\) there are unique integers \(q,r\) that satisfy

\begin{align*}
n=mq + r, \amp \amp 0\leq r\lt m.
\end{align*}

The number \(q\) is called the quotient and the number \(r\) is called the remainder for dividing \(n\) by \(m\).

Every positive integer \(n\) can be written as a product of primes. Further, this prime factorization is unique. That means that if

\begin{equation*}
n=p_1p_2\cdots p_k=q_1q_2\cdots q_\ell
\end{equation*}

for primes \(p_i,q_j\text{,}\) then \(k=\ell\) and there is a rearrangement of the subscripts for which \(p_i=q_i\) for \(1\leq i\leq k\text{.}\)

Here is a useful corollary that relates divisibility to the Division Algorithm.

Let \(m\) be a positive integer, let \(n\) be any integer, and let \(n=qm+r\text{,}\) where \(q,r\) are integers, with \(r\) in the range \(0\leq r\lt
m\text{,}\) as guaranteed by the Division Algorithm. Then we have \(m|n\) if and only if \(r=0\text{.}\)

Suppose \(r=0\text{.}\) Then \(n=mq+r\) reduces to \(n=mq\text{,}\) so \(m|n\text{.}\) Conversely, suppose that \(m|n\text{.}\) Then we have \(n=mk\) for some integer \(k\text{.}\) The Division algorithm says that \(n=mq+r\) is the *only* possible way to write \(n\) as a multiple of \(m\) with a remainder in the range \(0\leq r\lt m\text{.}\) Therefore we conclude that \(q=k\) and \(r=0\text{.}\)

- If \(r=0\text{,}\) then \(m|n\text{.}\)
- If \(m|n\text{,}\) then \(r=0\text{.}\)

It is often a good idea to construct a proof for an "if and only if" statement in two parts, one part for each of the two "if-then" statements. Statement 1 is called the "if" part of the "if and only if" statement, and statement 2 is called the "only if" part of the if and only if statement.

Here is a fact that demonstrates the power of the Division Algorithm and the Fundamental Theorem of Arithmetic.

There are infinitely many prime numbers.

We wish to show that there are infinitely many primes. Suppose, on the contrary, that there exist only finitely many primes, say \(p_1,p_2,\ldots,p_r\text{.}\) Let \(s=p_1p_2\cdots
p_r+1\text{.}\) Using the division algorithm to divide \(s\) by \(p_1\text{,}\) we have \(s= p_1q+r\) with \(q=p_2p_3\cdots p_r\) and \(r=1\text{.}\) By Corollary 1.3.4, the fact that \(r=1\) means that \(p_1\) does *not* divide \(s\text{,}\) so \(p_1\) cannot appear in the prime factorization of \(s\text{.}\) A similar argument shows that none of the \(p_j\)’s can appear in the prime factorization of \(s\text{.}\) This contradicts the Fundamental Theorem of Arithmetic, that says \(s\) can be expressed as a product of primes. We conclude that there are infinitely many primes.

We write \(\Z_m\) to denote the set

\begin{equation*}
\Z_m = \{0,1,\ldots,m-1\}
\end{equation*}

of possible remainders obtained when dividing by a positive integer by \(m\text{.}\) The function \(\Z \to \Z_m\) that sends an input \(n\) to its remainder when dividing by \(m\) is called "reducing mod \(m\)". Sometimes we write \(n \MOD m\), pronounced "\(n\) modulo \(m\)" or simply "\(n\) mod \(m\)", to denote this remainder.

We define operations \(a+_m b\) and \(a\cdot_m b\) for elements \(a,b\) in \(\Z_m\) by

\begin{align*}
a+_m b \amp = (a+b)\MOD m\\
a\cdot_m b \amp = (ab)\MOD m
\end{align*}

The operations \(+_m\text{,}\) \(\cdot_m\) are called addition modulo \(m\) and multiplication modulo \(m\), respectively. The set \(\Z_m\) is sometimes called the "\(m\)-hour clock" and the operations \(+_m,\cdot_m\) are called "clock arithmetic" or "arithmetic modulo \(m\)".

Find examples of integers \(m\gt
1\text{,}\) \(a,b\in \Z_m\) such that

- \(\displaystyle a+_m b = 0\)
- \(a \cdot_m b = 0\) and \(a\neq 0\) and \(b\neq 0\)
- \(a \cdot_m b =1\) and \(a\neq 1\) and \(b\neq 1\)

Here is a useful fact that connects equivalence modulo an integer \(m\) with the operation that send an integer \(n\) to \(n \MOD m\text{.}\)

Let \(m>1\) be a positive integer, and let \(a,b\) be integers. Then \(a\equiv b \pmod{m}\) if and only if \(a\MOD m = b \MOD m\text{.}\)

Use the division algorithm to write

\begin{align*}
a \amp = qm + r\\
b \amp = q'm + r'
\end{align*}

for some integers \(q,q'\) and \(r,r'\) in the range \(0\leq r,r'\lt m\text{,}\) so we have

\begin{equation}
a-b = (q-q')m + (r-r')\tag{1.3.1}
\end{equation}

with \(r-r'\) in the range \(-(m-1)\leq r-r'\leq m-1\text{.}\) To establish the "if" part of the statement in the Proposition, suppose that \(a \MOD m = b\MOD m\text{.}\) This means that \(r=r'\text{,}\) so (1.3.1) becomes \(a-b=(q - q')m\text{.}\) Thus we have \(m|(a-b)\text{,}\) so we conclude that \(a\equiv b \pmod{m}\text{.}\) To establish the "only if" part of the statement in the Proposition, suppose that \(a\equiv b \pmod{m}\text{,}\) so we have that \(a-b\) is a multiple of \(m\text{,}\) say \(a-b=km\text{.}\) Then (1.3.1) becomes

\begin{equation*}
r-r' = m(k-q+q').
\end{equation*}

Because \(-(m-1)\leq r-r'\leq m-1\text{,}\) we conclude that \(k-q+q'\) must be zero. Thus we have \(r=r'\text{,}\) which means that \(a \MOD m = b\MOD m\text{.}\) This completes the proof.

Let \(m\) be a positive integer.

- Show that \(a\equiv a \pmod{m}\) for every integer \(a\text{.}\) (This is called the
*reflexive*property of equivalence modulo \(m\text{.}\)) - Show that if \(a\equiv b \pmod{m}\) then \(b\equiv a \pmod{m}\text{.}\) (This is called the
*symmetric*property of equivalence modulo \(m\text{.}\)) - Show that if \(a\equiv b \pmod{m}\) and \(b\equiv c \pmod{m}\text{,}\) then \(a\equiv c \pmod{m}\text{.}\) (This is called the
*transitive*property of equivalence modulo \(m\text{.}\))

Let \(m\) be a positive integer. Show that if \(a_1\equiv b_1 \pmod{m}\) and \(a_2\equiv b_2
\pmod{m}\text{,}\) then

- \(a_1+a_2\equiv b_1+b_2 \pmod{m}\text{,}\) and
- \(a_1a_2\equiv b_1b_2 \pmod{m}\text{.}\)

Prove the following property of modular arithmetic, called the *distributive law*. For any positive integer \(m\text{,}\) we have

\begin{equation}
a\cdot_m (b+_m c) = (a\cdot_m b)
+_m (a\cdot_m c)\tag{1.3.2}
\end{equation}

for all \(a,b,c\) in \(\Z_m\text{.}\)

By the ordinary distributive law for integers, we have

\begin{equation*}
a(b+c)=ab+ac.
\end{equation*}

It follows that

\begin{equation*}
a(b+c)\equiv ab+ac \pmod{m}
\end{equation*}

Now use Exercise 1.3.3 to show that

\begin{equation*}
a(b+c) \equiv a\cdot_m (b+_m c) \pmod{m}.
\end{equation*}

and

\begin{equation*}
ab+ac \equiv [(a\cdot_m b) +_m (a\cdot_m c)] \pmod{m}.
\end{equation*}

Suppose that \(m\) is not prime. Show that there exist nonzero elements \(a,b\) in \(\Z_m\) for which there exists *no* \(x\) in \(\Z_m\) such that \(ax\equiv b \pmod{m}\text{.}\)

Let \(m\) be a prime. Let \(a\) be a nonzero element of \(\Z_m\) and let \(b\) be any element of \(\Z_m\text{.}\) Show that there exists some \(x\) in \(\Z_m\) such that \(ax\equiv b \pmod{m}\text{.}\) Hint: consider the function \(\mu_a\colon \Z_m \to \Z_m\) given by \(n\to an \MOD m\text{.}\) Notice that \(ax\equiv b
\pmod{m}\) is the same thing as \(\mu_a(x)=b\) (say why!). Show that \(\mu_a\) is one-to-one, then cite an appropriate result from these Notes to conclude that \(\mu_a\) is onto. Finally, explain how this solves the problem by guaranteeing the existence of the \(x\) that you need.