A set is a collection of mathematical objects.
The set of integers is denoted by \(\mathbb{Z}\).
The set of natural numbers is denoted by \(\mathbb{N}\).
The set of rational numbers is denoted by \(\mathbb{Q}\).
The set of real numbers is denoted by \(\mathbb{R}\).
For a set \(S\), we write \(a \in S\) to express that \(a\) is a member or element of \(S\). For example, \(x \in \mathbb{Z}\) expresses that \(x\) is an integer.
To specify that \(x_1,\ldots,x_k\), where \(k\) is a positive integer, are members of same set \(S\), we may write \(x_1,\ldots,x_k \in S\).
Definition. An integer \(m\) is said to be even if \(m = 2k\) for some integer \(k\). An integer that is not even is said to be odd.
Definition. Let \(n,d\in \mathbb{Z}\) with \(d \neq 0\). We say \(d\) divides \(n\), denoted by \(d \mid n\), if there exists an integer \(k\) such that \(n = kd\). We call \(n\) an integer multiple of \(d\) and \(d\) a divisor (or factor) of \(n\).
If \(a\) does not divide \(b\), we write \(a \nmid b\).
\(3 \mid 15\)
\(-2 \mid 6\)
\(4 \nmid 6\)
Let \(a,b,c\in \mathbb{Z}\) with \(a \neq 0\) and \(b \neq 0\). If \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
To see this, note that \(a \mid b\) implies \(b = x a\) for some \(x\in \mathbb{Z}\) and \(b \mid c\) implies \(c = y b\) for some \(y\in \mathbb{Z}\). Thus, \(c = yb = y (xa ) = (yx) a\). But \(yx\) is an integer. By definition, \(a \mid c\).
Theorem 1.4.3. Given integers \(n\) and \(d \gt 0\), there are unique integers \(q\) and \(r\) such that \(n = dq + r\) and \(0 \leq r \lt d\).
The above theorem is sometimes known as the quotient-remainder theorem.
For \(d =2\), it says that every integer \(n\) can be written as \(2q + 0\) or \(2q + 1\). Thus, every odd number can be written as \(2k+1\) for some integer \(k\).
For \(d =3\), it says that every integer \(n\) can be written as \(3q + 0\), \(3q + 1\), or \(3q + 2\).
\(q\) is called the quotient and \(r\) is called the remainder.
Suppose that \(a,b \in \mathbb{Z}\) have the same remainder \(r\) when divided by \(n\) where \(n \in \mathbb{N}, n \geq 2\). Then by Theorem 1.4.3, we have \[\begin{eqnarray*} a = n q_1 + r \\ b = n q_2 + r \\ \end{eqnarray*}\] for some integers \(q_1,q_2\). Then, \(a -b = n(q_1 - q_2)\). Since \(q_1 - q_2 \in \mathbb{Z}\), \(n \mid (a-b)\) by definition.
One can also show that if \(n \mid (a-b)\), then \(a\) and \(b\) have the same remainder when divided by \(n\).
Definition. Let \(a,b \in \mathbb{Z}\). Let \(n \in \mathbb{N}, n\geq 2\). We say that \(a\) is congruent to \(b\) modulo \(n\), denoted by \(a \equiv b~(\text{mod}~n)\), if \(n \mid (a-b)\). If \(n \nmid (a-b)\), we write \(a \not \equiv b~(\text{mod}~n)\).
The number \(n\) is called the modulus.
\(15 \equiv 1~(\text{mod}~7)\) since \(7 \mid (15 -1 )\).
\(3 \equiv -1~(\text{mod}~4)\) since \(4 \mid (3 - (-1) )\).
\(2 \not \equiv 15~(\text{mod}~7)\) since \(7 \nmid (2 - 15)\).
\(10^{10} \equiv -100~(\text{mod}~5^2)\) since \(5^2 \mid (10^{10} - (-100))\).
Facts. Let \(n \in \mathbb{N}, n\geq 2\). Let \(a \in \mathbb{Z}\). Then
\(n \equiv 0~(\text{mod}~n)\);
\(a \equiv a~(\text{mod}~n)\);
if \(a \equiv 0~(\text{mod}~n)\), then \(n \mid a\);
if \(a\) has remainder \(r\) when divided by \(n\), then \(a \equiv r~(\text{mod}~n)\).
if \(a \equiv r~(\text{mod}~n)\) and \(0 \leq r \lt n\), then \(a\) has remainder \(r\) when divided by \(n\).
If \(a \equiv b~(\text{mod}~n)\) and \(b \equiv c~(\text{mod}~n)\), then \(a \equiv c~(\text{mod}~n).\)
Proposition A1. Let \(a,b,c,d,n \in \mathbb{Z}\) with \(n\geq 2\). If \(a \equiv b~(\text{mod}~n)\) and \(c \equiv d~(\text{mod}~n)\), then \(a+c \equiv b+d~(\text{mod}~n)\) and \(ac \equiv bd~(\text{mod}~n)\).
For example, if \(x \equiv -1~(\text{mod}~3)\), then \(x\cdot x \equiv (-1)(-1)~(\text{mod}~3)\), giving \(x^2 \equiv 1~(\text{mod}~3)\).
Proposition A2. Let \(a,b \in \mathbb{Z}\). Let \(k,n \in \mathbb{N}, n\geq 2\). If \(a \equiv b~(\text{mod}~n)\), then \(a^k \equiv b^k~(\text{mod}~n)\).
Note that \(a \equiv b~(\text{mod}~n)\) means that \(a - b = n x\) for some \(x \in \mathbb{Z}\).
Now, \(a^k - b^k = (a-b) (a^{k-1}+ a^{k-2}b + \cdots + ab^{k-2} + b^{k-1})\). Hence, \(a^k - b^k = nx (a^{k-1}+ a^{k-2}b + \cdots + ab^{k-2} + b^{k-1}) = nm\) where \(m\) is the integer \(x (a^{k-1}+ a^{k-2}b + \cdots + ab^{k-2} + b^{k-1})\). Thus, \(n \mid (a^k - b^k)\), giving \(a^k \equiv b^k~(\text{mod}~n)\).
An important result in number theory that we will state without proof is the fundamental theorem of arithmetic. It is also called the unique factorization theorem. It states that every integer at least 2 is a prime or is the product of prime numbers and that the product is unique, up to the ordering of the factors.
Show that \(2^{33} \equiv 1~(\text{mod}~7)\).
Solution. To see this, note that \(8 \equiv 1~(\text{mod}~7)\). Thus, \(2^3 \equiv 1~(\text{mod}~7)\). By Proposition A2, \((2^3)^{11} \equiv 1^{11}~(\text{mod}~7)\), giving \(2^{33} \equiv 1~(\text{mod}~7)\).
Show that \(11^{n+2} + 12^{2n+1}\) is divisible by \(133\) for all natural numbers \(n\).
Solution. We need to show that \(11^{n+2} + 12^{2n+1} \equiv 0~(\text{mod}~133)\).
Note that \(11^{n+2} + 12^{2n+1} = 121\cdot 11^n + 12\cdot 144^n\). Now, \(144 \equiv 11~(\text{mod}~133)\). Thus, \(144^n \equiv 11^n~(\text{mod}~133)\) by Proposition A2. By Proposition A1, we have \(12\cdot 144^n \equiv 12\cdot 11^n~(\text{mod}~133)\).
Now, \(121 \equiv -12~(\text{mod}~133)\). Hence, \(121\cdot 11^n \equiv -12\cdot 11^n~(\text{mod}~133)\) by Proposition A1.
By Proposition A1, we have \(11^{n+2} + 12^{2n+1} \equiv -12\cdot 11^n+ 12 \cdot 11^n~(\text{mod}~133)\), giving \(11^{n+2} + 12^{2n+1} \equiv 0~(\text{mod}~133)\) as desired.
Show that \(6^{1800} \equiv 1~(\text{mod}~7)\).
Show that \(3^{2017} \equiv 3~(\text{mod}~8)\).
Let \(k\) be a positive odd integer. Show that \(3^k + 5^k \equiv 0 ~(\text{mod}~4)\).
Show that \(6^k \equiv 6~(\text{mod}~10)\) for every positive integer \(k\). (Hint: Take a look at the proof of Proposition A2.)
Let \(x \in \mathbb{Z}\). Show that \(x^3 \equiv x~(\text{mod}~3)\).
Let \(n\), \(a\), \(b\) be natural numbers with \(n > 0\). Show that if \(n \mid (a-b)\), then \(a\) and \(b\) have the same remainder when divided by \(n\).