Preliminaries

For $n = 5, 8, 12, 20$, and $25$, find all positive integers less than $n$ and relatively prime to $n$.

Determine

Determine $51 \bmod 13$, $342 \bmod 85$, $62 \bmod 15$, $10 \bmod 15$, $(82 \cdot 73) \bmod 7$, $(51+68) \bmod 7$, $(35 \cdot 24) \bmod 11$, and $(47+68) \bmod 11$.

Find integers $s$ and $t$ such that $1 = 7 \cdot s + 11 \cdot t$. Show that $s$ and $t$ are not unique.

Prove that every integer that is a common multiple of every member of a finite set of integers is a multiple of the least common multiple of those integers.

Prove that for any three consecutive integers $n$, $n + 1$, $n + 2$ one must be divisible by $3$.

Show that if $a$ and $b$ are positive integers, then $ab = \lcm (a, b) \cdot \gcd (a, b)$.

Suppose $a$ and $b$ are integers that divide the integer $c$. If $a$ and $b$ are relatively prime, show that $ab$ divides $c$. Show, by example, that if $a$ and $b$ are not relatively prime, then $ab$ need not divide $c$.

If $a$ and $b$ are integers and $n$ is a positive integer, prove that $a \bmod n = b \bmod n$ if and only if $n$ divides $a - b$.

Let $d = \gcd (a, b)$. If $a = da'$ and $b = db'$, show that $\gcd (a', b') = 1$.

Let $n$ be a fixed positive integer greater than $1$. If $a \bmod n = a'$ and $b \bmod n = b'$, prove that $(a+b) \bmod n = (a'+b') \bmod n$ and $(ab) \bmod n = (a'b') \bmod n$. (This exercise is referred to in Chapters 6, 8, 10, and 15.)

Let $a$ and $b$ be positive integers and let $d = \gcd (a, b)$ and $m = \lcm (a, b)$. If $t$ divides both $a$ and $b$, prove that $t$ divides $d$. If $s$ is a multiple of both $a$ and $b$, prove that $s$ is a multiple of $m$.

Let $n$ and $a$ be positive integers and let $d = \gcd (a, n)$. Show that the equation $ax \bmod n = 1$ has a solution if and only if $d = 1$. (This exercise is referred to in Chapter 2.)

Theorem 0.2 (GCD is a Linear Combination) states: for any nonzero integers $a$ and $b$, there exist integers $s$ and $t$ such that $\gcd (a, b) = as + bt$; moreover, $\gcd (a, b)$ is the smallest positive integer of the form $as + bt$. Its corollary states: integers $a$ and $b$ are relatively prime if and only if there exist integers $s$ and $t$ such that $as + bt = 1$.

Show that $5n + 3$ and $7n + 4$ are relatively prime for all $n$.

Suppose that $m$ and $n$ are relatively prime and $r$ is any integer. Show that there are integers $x$ and $y$ such that $mx + ny = r$.

Let $p$, $q$, and $r$ be primes other than $3$. Show that $3$ divides $p^2 + q^2 + r^2$.

Prove that every prime greater than $3$ can be written in the form $6n + 1$ or $6n + 5$.

Determine $7^{1000} \bmod 6$ and $6^{1001} \bmod 7$.

Let $a$, $b$, $s$, and $t$ be integers. If $a \bmod st = b \bmod st$, show that $a \bmod s = b \bmod s$ and $a \bmod t = b \bmod t$. What condition on $s$ and $t$ is needed to make the converse true? (This exercise is referred to in Chapter 8.)

If $n$ is an integer greater than $1$ and $(n - 1)! \equiv 1 \pmod n$, prove that $n$ is prime.

Show that $\gcd (a, bc) = 1$ if and only if $\gcd (a, b) = 1$ and $\gcd (a, c) = 1$. (This exercise is referred to in Chapter 8.)

Let $p_1, p_2, \ldots , p_n$ be primes. Show that $p_1 p_2 \cdots p_n + 1$ is divisible by none of these primes.

Prove that there are infinitely many primes.

For any complex numbers $z_1$ and $z_2$, prove that $\left|z_1 z_2\right| = \left|z_1\right|\left|z_2\right|$.

Give an if and only if'' statement that describes when the logic gate $x$ NAND $y$ modeled by $1 + xy$ is $1$. Give an if and only if'' statement that describes when the logic gate $x$ XNOR $y$ modeled by $1 + x + y$ is $1$.

For inputs of $0$ and $1$ and mod $2$ arithmetic describe the output of the formula $z + xy + xz$ in the form ``If $x \ldots$, else $\ldots$.''

For every positive integer $n$, prove that a set with exactly $n$ elements has exactly $2^n$ subsets (counting the empty set and the entire set).

Prove that $2^n 3^{2n} - 1$ is always divisible by $17$.

Prove that there is some positive integer $n$ such that $n, n + 1, n + 2, \ldots , n + 200$ are all composite.

If $p$ is a prime and $p$ divides $a_1 a_2 \ldots a_n$, prove that $p$ divides $a_i$ for some $i$.

Use the Generalized Euclid's Lemma (see Exercise 0.30) to establish the uniqueness portion of the Fundamental Theorem of Arithmetic.

The Fundamental Theorem of Arithmetic (Theorem 0.3) states: every integer greater than $1$ is a prime or a product of primes, and this product is unique except for the order in which the factors appear; that is, if $n = p_1 p_2 \cdots p_r$ and $n = q_1 q_2 \cdots q_s$, where the $p$'s and $q$'s are primes, then $r = s$ and, after renumbering the $q$'s, $p_i = q_i$ for all $i$.

What is the largest bet that cannot be made with chips worth $7.00 and $9.00? Verify that your answer is correct with both forms of induction.

Prove that the First Principle of Mathematical Induction is a consequence of the Well Ordering Principle.

The Fibonacci numbers are $1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$. In general, the Fibonacci numbers are defined by $f_1 = 1$, $f_2 = 1$, and for $n \geq 3$, $f_n = f_{n-1} + f_{n-2}$. Prove that the $n$th Fibonacci number $f_n$ satisfies $f_n < 2^n$.

Prove by induction on $n$ that for all positive integers $n$, $n^3 + (n + 1)^3 + (n + 2)^3$ is a multiple of $9$.

Suppose that there is a statement involving a positive integer parameter $n$ and you have an argument that shows that whenever the statement is true for a particular $n$ it is also true for $n + 2$. What remains to be done to prove the statement is true for every positive integer? Describe a situation in which this strategy would be applicable.

In the cut ``As'' from Songs in the Key of Life, Stevie Wonder mentions the equation $8 \times 8 \times 8 = 4$. Find all integers $n$ for which this statement is true, modulo $n$.

Prove that for every integer $n$, $n^3 \bmod 6 = n \bmod 6$.

If it is 2:00 a.m.now, what time will it be 3736 hours from now?

Determine the check digit for a money order with identification number $7234541780$.

Suppose that in one of the noncheck positions of a money order number, the digit $0$ is substituted for the digit $9$ or vice versa. Prove that this error will not be detected by the check digit. Prove that all other errors involving a single position are detected.

Suppose that a money order identification number and check digit of $21720421168$ is erroneously copied as $27750421168$. Will the check digit detect the error?

A transposition error involving distinct adjacent digits is one of the form $\ldots ab \ldots \to \ldots ba \ldots$ with $a \neq b$. Prove that the money order check-digit scheme will not detect such errors unless the check digit itself is transposed.

Explain why the check digit for a money order for the number $N$ is the repeated decimal digit in the real number $N \div 9$.

The 10-digit International Standard Book Number (ISBN-10) $a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}$ has the property $(a_1, a_2, \ldots , a_{10}) \cdot (10, 9, 8, 7, 6, 5, 4, 3, 2, 1) \bmod 11 = 0$. The digit $a_{10}$ is the check digit. When $a_{10}$ is required to be $10$ to make the dot product $0$, the character X is used as the check digit. Verify the check digit for the ISBN-10 assigned to this book.

Suppose that an ISBN-10 has a smudged entry where the question mark appears in the number $0\text{-}716?\text{-}2841\text{-}9$. Determine the missing digit.

Suppose three consecutive digits $abc$ of an ISBN-10 are scrambled as $bca$. Which such errors will go undetected?

Let $S$ be the set of real numbers. If $a, b \in S$, define $a \sim b$ if $a - b$ is an integer. Show that $\sim$ is an equivalence relation on $S$. Describe the equivalence classes of $S$.

Let $S$ be the set of integers. If $a, b \in S$, define $aRb$ if $ab \geq 0$. Is $R$ an equivalence relation on $S$?

Let $S$ be the set of integers. If $a, b \in S$, define $aRb$ if $a + b$ is even. Prove that $R$ is an equivalence relation and determine the equivalence classes of $S$.

Complete the proof of Theorem 0.7 by showing that $\sim$ is an equivalence relation on $S$.

Theorem 0.7 (Equivalence Classes Partition) states: the equivalence classes of an equivalence relation on a set $S$ constitute a partition of $S$; conversely, for any partition $P$ of $S$, there is an equivalence relation on $S$ whose equivalence classes are the elements of $P$. The proof of the converse begins: let $P$ be a collection of nonempty disjoint subsets of $S$ whose union is $S$; define $a \sim b$ if $a$ and $b$ belong to the same subset in the collection. It remains to show that $\sim$ is an equivalence relation on $S$.

Prove that $3$, $5$, and $7$ are the only three consecutive odd integers that are prime.