Number theory basics
Relevant readings: Lehman, et al. 9.1–9.4, 9.6–9.7, 9.9–9.10
Note: We’ll take the proofs of the results here for granted in this course, but you can check the reference above for the full proofs if you’re interested.
Aged like milk…
Put simply, number theory is the study of the integers. Why? What’s with \(10\) or \(1\) or \(-4000\) that you don’t understand? For this reason many people (and even mathematicians) back then thought that number theory is a useless field, and also because it was “well-detached” from other fields of math. But the famous number theorist G. H. Hardy delights from the fact that it was useless and impractical:
[Number theorists] may be justified in rejoicing that there is one science, at any rate, and that their own, whose very remoteness from ordinary human activities should keep it gentle and clean.
And so he confidently concluded that:
Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.
To give some context, Hardy wrote his essay A Mathematician’s Apology (where these quotes came from) in 1940. A few years later, the Manhattan Project was formed, doing research and development on nuclear weapons for which breakthroughs in quantum mechanics and relativity had made them possible. About thirty years later, public-key cryptography (and modern cryptography as a whole) was born, which makes secure communication possible. If anything, there is a “warlike purpose” for secure communication, and in fact that’s critical in war. (Do you see now why the NSA hires mathematicians?) Today, cryptosystems based on large prime numbers help make the Internet secure.
As number theory underlies modern cryptography, Hardy’s claim aged spectacularly like milk, leaving him spinning in his grave…
Divisibility
We say that \(a\) divides \(b\),1 denoted by \(a \mid b\), iff there is an integer \(k\) such that $$ak = b.$$ This implies that for all \(n\), the following statements hold true:
-
\(n \mid 0\)
-
\(n \mid n\)
-
\(\pm 1 \mid n\), and
-
\(0 \mid n\) implies \(n=0\).
Facts about divisibility
We present here some basic facts about divisibility.
Let \(a, b, c\) be integers. We have:
-
If \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
-
If \(a \mid b\) and \(a \mid c\), then \(a \mid sb + tc\) for all \(s\) and \(t\).
-
For all \(c \ne 0\), \(a \mid b\) if and only if \(ca \mid cb\).
Euclidean division
Recall from your grade school math that when a number does not cleanly divide another, a remainder is left over. We can state this formally as follows:
Let \(n\) and \(d\) be integers such that \(d \ne 0\). Then there exists a unique pair of integers \(q\) and \(r\), such that $$n = q \cdot d + r \quad\text{and}\quad 0 \le r < \left|d\right|.$$ Here, \(q\) is the quotient and \(r\) is the remainder.
The remainder operator
For any integer \(a\) and \(b\), the remainder when \(a\) is divided by \(b\) is denoted by \(a \bmod b\): $$a \bmod b = a - \left\lfloor a/b \right\rfloor \cdot b$$ where \(\lfloor a/b \rfloor\) is the (integer) quotient of \(a\) and \(b\).
Due to the division theorem, the remainder is guaranteed to be nonnegative regardless of the sign of \(a\) and \(b\). So \(-10 \bmod 3 = 2\), since \(-10 = (-4)\cdot 3 + 2\).
It’s quite unfortunate that different programming languages treat remainder operations inconsistently. For example, C, C++, and Java follow the sign of the first argument, so the expression would evaluate to \(-1\), while Python follows the sign of the second argument, so the expression would correctly evaluate to \(2\), but outputs \(-1\) instead. Always remember that remainders are nonnegative!
Greatest common divisors
The greatest common divisor of two integers \(a\) and \(b\), denoted by \(\gcd(a, b)\), is the largest integer that divides them both. If \(\gcd(a, b) = 1\), then we say that \(a\) and \(b\) are relatively prime or coprime.
Based from our definition, these statements are true: $$\begin{align} \gcd(n, 1) &= 1 \\ \gcd(n, n) &= \gcd(n, 0) = \left| n \right| \quad\text{for $n \ne 0$}.\end{align}$$
-
\(\gcd(69, 420) = 3\) since \(3\) is the largest integer that divides both \(69\) and \(420\).
-
\(\gcd(9, 22) = 1\) since \(1\) is the largest integer that divides both \(9\) and \(22\). As such, \(9\) and \(22\) are relatively prime.
Euclid’s algorithm
How do we find gcd’s? One way is to use an algorithm due to Euclid, which is based on the following observation.
In other words, we can then recursively define \(\gcd(a, b)\) as $$\gcd(a, b) = \begin{cases} a & \text{if $b = 0$}, \\ \gcd(b, a \bmod b) & \text{otherwise}. \end{cases}$$
We could compute the greatest common divisor of \(1147\) and \(899\) by repeatedly applying the above definition: $$\begin{align} \gcd(1147, 899) &= \gcd(899, 1147 \bmod 899) = \gcd(899, 248) \\ &= \gcd(248, 899 \bmod 248) = \gcd(248, 155) \\ &= \gcd(155, 248 \bmod 155) = \gcd(155, 93) \\ &= \gcd(93, 155 \bmod 93) = \gcd(93, 62) \\ &= \gcd(62, 93 \bmod 62) = \gcd(93, 31) \\ &= \gcd(31, 62 \bmod 31) = \gcd(31, 0) \\ &= 31. \end{align}$$
Extended Euclidean algorithm
The greatest common divisor of \(a\) and \(b\) is a linear combination of \(a\) and \(b\). That is, $$\gcd(a, b) = sa + tb$$ for some integers \(s\) and \(t\).
To find \(s\) and \(t\), we follow Euclid’s algorithm as usual, but we’ll do some extra bookkeeping. More specifically we keep track of how to write each of the remainders as a linear combination of \(a\) and \(b\).
We can compute the gcd of \(420\) and \(96\) with the “additional bookkeeping” as follows:
| \(x\) | \(y\) | \(x \bmod y\) | \(=\) | \(x - \lfloor x/y \rfloor \cdot y\) |
|---|---|---|---|---|
| \(420\) | \(96\) | \(36\) | \(=\) | \(420 - 4 \cdot 96\) |
| \(96\) | \(36\) | \(24\) | \(=\) | \(96 - 2 \cdot 36\) |
| \(=\) | \(96 - 2 \cdot (420 - 4 \cdot 96)\) | |||
| \(=\) | \(-2 \cdot 420 + 9 \cdot 96\) | |||
| \(36\) | \(24\) | \(12\) | \(=\) | \(36 - 1 \cdot 24\) |
| \(=\) | \((420 - 4 \cdot 96) - 1 \cdot (-2 \cdot 420 + 9 \cdot 96)\) | |||
| \(=\) | \(\boxed{3 \cdot 420 - 13 \cdot 96}\) | |||
| \(24\) | \(12\) | \(0\) |
Along the way, we computed the remainder \(x \bmod y\). Then in this linear combination of \(x\) and \(y\), we rewrite \(x\) and \(y\) in terms of \(420\) and \(96\) using our previous computations.
The last nonzero remainder is the gcd, which in this case is \(12\), and we can write it as a linear combination of \(420\) and \(96\): \(12 = 3 \cdot 420 - 13 \cdot 96\).
Prime numbers
A prime is a number greater than \(1\) that is divisible only by itself and \(1\). A number other than \(0\), \(1\), and \(-1\) that is not a prime is called composite.
Counting primes
The distribution of prime numbers seem almost random, but one of the great insights about primes is that their density among the integers has a precise limit.
Let \(\pi(n)\) denote the number of primes up to \(n\), so $$\pi(n) = \Len{\Set{p \in \Set{2, \ldots, n} \mid \text{$p$ is prime}}}.$$
Though the spacing between consecutive primes seem erratic, it eventually smooths out to be the same as the growth of the function \(n / \ln n\).
It’s a surprise tool that will help us later, when we discuss about algorithms for factoring integers.
Fundamental theorem of arithmetic
An important fact you should remember is that every positive integer has a unique prime factorization, meaning every positive integer can be constructed from primes in exactly one way (ignoring the order of the factors).
More concretely, a positive integer \(n\) can be written as $$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ where \(p_1, p_2, \ldots, p_k\) are unique primes. We will call this as the prime factorization of \(n\).
This is one of the reasons why \(1\) is not considered as a prime, otherwise unique factorization wouldn’t hold anymore for integers.
Modular arithmetic
Modular arithmetic operates like a clock, where it only works within a finite set of integers and numbers “wrap around” at a certain number.
Congruences
If \(a\) and \(b\) both have the same remainder when divided by \(n\), then we say that \(a\) and \(b\) are congruent modulo \(n\), usually written as \(a \equiv b \pmod{n}\). That is: $$a \bmod n = b \bmod n \quad\text{implies}\quad a \equiv b \pmod{n}.$$ The converse is also true, but we won’t prove it here.
We’ll also make use of the following lemma which would be helpful when we deal with arithmetic modulo \(n\):
Doing arithmetic modulo \(n\) [doing-arithmetic-modulo-n]
One of the main motivations behind doing arithmetic modulo \(n\) is
due to the limitation of computers. For example in most programming
languages, an int can only handle numbers up to \(2^{31}-1\) (I
think), thus an overflow would be inevitable if we start working with
very large numbers. One way to avoid integer overflow is to take
remainders at every step so that the entire computation only involves
number in the range, namely \(\Set{0, 1, \ldots, n-1}\).
Suppose we want to determine the tens digit of \(2^{2022} + 42069\). The sure-fire way to find would be to evaluate the whole expression, but we would risk overflowing if we were to store this as an integer data type since this has at least \(600\) digits. Instead, we can get the remainder of that whole thing when divided by \(100\).
The remainder when \(42069\) is divided by \(100\) is \(69\). It would be tempting to directly compute \(2^{2022}\) and get the remainder, but don’t. Let’s try to look for a pattern. $$\begin{array}{r|cccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline 2^n \bmod 100 & 2 & 4 & 8 & 16 & 32 & 64 & 28 & 56 & 12 & 24 & 48 & 96 & 92 & 84 \end{array}$$ $$\begin{array}{r|ccccccccccccccc} n & 15 & 16 & 17 & 18 & 19 & 20 & 21 &22 & 23 & 24 & 25 & 26 & \cdots \\ \hline 2^n \bmod 100 & 68 & 36 & 72 & 44 & 88 & 76 & 52 & 4 & 8 & 16 & 32 & 64 & \cdots \end{array}$$ We can see that after \(2^{21} \bmod 100 = 52\), it repeats back to \(4, 8, 16, \ldots\), thus we have a “cycle” of \(20\) numbers. Since \(2022 = 101 \cdot 20 + 2\), we have: $$\begin{align} &\left(2^{2022} + 42069\right) \bmod 100 \\ &= \left(2^{2022} \bmod 100 + 42069 \bmod 100\right) \bmod 100 \\ &= \left(\left(2^{101 \cdot 20 + 2}\right) \bmod 100 + 69\right) \bmod 100 \\ &= \left(\left(2^{2020} \cdot 4 \right) \bmod 100 + 69\right) \bmod 100 \\ &= \left(\left(2^{2020} \bmod 100 \cdot 4 \bmod 100\right) + 69\right) \bmod 100 \\ &= \left(\left(2^{20} \bmod 100 \cdot 4 \bmod 100\right) + 69\right) \bmod 100 \\ &= \left(\left(76 \cdot 4\right) + 69\right) \bmod 100 \\ &= 373 \bmod 100 \\ &= 73. \end{align}$$
Since \(\left(2^{2022} + 42069\right) \bmod 100 = 73\), the tens digit is \(7\).
Introducing \(\ZZ_n\)
Why does that work? Let’s introduce some new notation, namely \(+_n\) for doing an addition and then immediately taking a remainder on division by \(n\), and similarly \(\cdot_n\) for multiplication: $$\begin{align} i +_n j &= \left(i + j\right) \bmod n \\ i \cdot_n j &= \left(i j\right) \bmod n\end{align}$$
To be able to add and multiply within integers modulo \(n\), we repeatedly apply the following lemma:
$$\begin{align} \left(i + j\right) \bmod n &= (i \bmod n) +_n (j \bmod n) \\ \left(i j\right) \bmod n &= (i \bmod n) \cdot_n (j \bmod n) \end{align}$$
The set of integers \(\Set{0, 1, \ldots, n-1}\), together with the operations \(+_n\) and \(\cdot_n\) is referred to as the ring of integers modulo \(n\), denoted by \(\ZZ_n\).2 To make things tidier, we just denote the operations as \(+\) and \(\cdot\) if \(n\) is implied from context.
It turns out that all the familiar rules of arithmetic also hold in \(\ZZ_n\); in particular these are true in \(\ZZ_n\):
-
associativity of \(\cdot\) and \(+\)
\((i \cdot j) \cdot k = i \cdot (j \cdot k)\) and \((i + j) + k = i + (j + k)\)
-
identity for \(\cdot\) and \(+\)
\(1 \cdot k = k \cdot 1 = k\) and \(0 + k = k + 0 = k\)
-
inverse for \(+\)
\(k + (-k) = 0\)
-
commutativity of \(\cdot\) and \(+\)
\(i \cdot j = j \cdot i\) and \(i + j = j + i\)
-
distributivity
\(i \cdot (j + k) = (i \cdot j) + (i \cdot k)\)
Multiplicative inverses
In regular arithmetic, we use division to “undo” a multiplication, so in this sense multiplication and division are inverses of each other. The multiplicative inverse of a number (say \(x\)) is another number \(x^{-1}\) such that $$x \cdot x^{-1} = 1.$$
Over \(\QQ\), the set of rational numbers, every rational number (except \(0\)) of the form \(a/b\) has an inverse \(b/a\). On the other hand, only \(1\) and \(-1\) have inverses over the integers. Over the ring \(\ZZ_n\), it’s a bit more complicated.
\(2\) is a multiplicative inverse of \(8\) in \(\ZZ_{15}\), since $$2 \cdot 8 = 1 \quad\text{(in $\ZZ_{15}$)}.$$
But \(3\) does not have a multiplicative inverse in \(\ZZ_{15}\). By contradiction, let’s say there was an inverse \(y\) for \(3\), so $$1 = 3 \cdot y \quad\text{(in $\ZZ_{15}$)}.$$ Then multiplying both sides by \(5\) we have $$\begin{align} 5 &= 5 \cdot (3 \cdot y) \\ &= (5 \cdot 3) \cdot y \\ &= 0 \cdot y \\ &= 0 \quad\text{(in $\ZZ_{15}$)} \end{align}$$ which leads to a contradiction, thus there can’t be any such inverse \(y\).
Finding inverses
The proof to the following theorem conveniently shows us how to compute for the inverse.
If \(k \in \ZZ_n\) is relatively prime to \(n\), then \(k\) has an inverse in \(\ZZ_n\).3
Proof. If \(k\) is relatively prime to \(n\), this means \(\gcd(n, k) = 1\). We can use the extended Euclidean algorithm to express \(1\) as a linear combination of \(n\) and \(k\): $$sn + tk = 1.$$ Working over \(\ZZ_n\), the equation becomes $$(s \bmod n \cdot n \bmod n) + (t \bmod n \cdot k \bmod n) = 1 \quad\text{(in $\ZZ_n$)}.$$ But \(n \bmod n = 0\) and \(k \bmod n = k\) since \(k \in \ZZ_n\), so we get $$t \bmod n \cdot k = 1 \quad\text{(in $\ZZ_n$)}.$$ Thus \(t \bmod n\) is a multiplicative inverse of \(k\). ◻
In fact, when we’re able to find an inverse, it is the only inverse for that number; in other words, inverses are unique when they exist.
Suppose we want to find the inverse of \(18\) in \(\ZZ_{101}\). Using the extended Euclidean algorithm:
| \(x\) | \(y\) | \(x \bmod y\) | \(=\) | \(x - \lfloor x/y \rfloor \cdot y\) |
|---|---|---|---|---|
| \(101\) | \(18\) | \(11\) | \(=\) | \(101 - 5 \cdot 18\) |
| \(18\) | \(11\) | \(7\) | \(=\) | \(18 - 1 \cdot 11\) |
| \(=\) | \(18 - 1 \cdot (101 - 5 \cdot 18)\) | |||
| \(=\) | \(- 1 \cdot 101 + 6 \cdot 18\) | |||
| \(11\) | \(7\) | \(4\) | \(=\) | \(11 - 1 \cdot 7\) |
| \(=\) | \((101 - 5 \cdot 18) - 1 \cdot (- 1 \cdot 101 + 6 \cdot 18)\) | |||
| \(=\) | \(2 \cdot 101 - 11 \cdot 18\) | |||
| \(7\) | \(4\) | \(3\) | \(=\) | \(7 - 1 \cdot 4\) |
| \(=\) | \((- 1 \cdot 101 + 6 \cdot 18) - 1 \cdot (2 \cdot 101 - 11 \cdot 18)\) | |||
| \(=\) | \(-3 \cdot 101 + 17 \cdot 18\) | |||
| \(4\) | \(3\) | \(1\) | \(=\) | \(4 - 1 \cdot 3\) |
| \(=\) | \((2 \cdot 101 - 11 \cdot 18) - 1 \cdot (-3 \cdot 101 + 17 \cdot 18)\) | |||
| \(=\) | \(\boxed{5 \cdot 101 - 28 \cdot 18}\) | |||
| \(3\) | \(1\) | \(0\) |
Since \(1 = 5 \cdot 101 - 28 \cdot 18\), the inverse of \(18\) in \(\ZZ_{101}\) is \(-28 \bmod 101 = 73\).
Chinese remainder theorem
Suppose I have a number that leaves a remainder of \(1\) when divided by \(3\), \(4\) when divided by \(5\), and \(6\) when divided by \(7\). What is my number?
An easy but naïve solution is to make a table of values of \(n \bmod 3\), \(n \bmod 5\), and \(n \bmod 7\) for each \(n = 0, \ldots, 104\). Then we try to find the value of \(n\) such that \(n \bmod 3 = 1\), \(n \bmod 5 = 4\), and \(n \bmod 7 = 6\). $$\begin{array}{lccccccccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \cdots & 33 & \mathbf{34} & \cdots \\ \hline n \bmod 3 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & \cdots & 0 & \mathbf{1} & \cdots \\ n \bmod 5 & 0 & 1 & 2 & 3 & 4 & 0 & 1 & 2 & 3 & 4 & 0 & \cdots & 3 & \mathbf{4} & \cdots \\ n \bmod 7 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 0 & 1 & 2 & 3 & \cdots & 5 & \mathbf{6} & \cdots \end{array}$$ Eventually we will find out that \(n = 34\) satisfies the above conditions. Thus \(34\) is my number.
However, this brute-force approach wouldn’t scale well when the moduli get very large. Here’s a better way:
Let \(m_1, \ldots, m_k\) be pairwise relatively prime, meaning for each pair of distinct \(i, j\) we have \(\gcd\left(m_i, m_j\right) = 1\). Then the system of congurences $$\begin{align} x &\equiv a_1 \pmod{m_1} \\ \phantom{x} &\vdots \\ x &\equiv a_k \pmod{m_k} \end{align}$$ has a solution for \(x\) modulo \(M = m_1 \cdots m_k\).
Proof sketch. For all \(i\), let \(y_i = M/m_i\) be the product of all the moduli except \(m_i\), and \(y_i^\prime\) be the inverse of \(y_i\) modulo \(m_i\). Then $$x = \sum_{i=1}^k a_i y_i y_i^\prime \quad\text{(in $\ZZ_M$)}$$ is the unique solution. ◻
Let’s use the same “guess my number” problem above, but this time we’ll use the Chinese remainder theorem. Essentially, the problem boils down to finding a solution to the system of congruences: $$\begin{align} x &\equiv 1 \pmod{3} \\ x &\equiv 4 \pmod{5} \\ x &\equiv 6 \pmod{7} \end{align}$$
To find the unique solution \(x\), we need to calculate for \(y_i\) and \(y_i^\prime\), which are $$\begin{align} y_1 &= 5 \cdot 7 = 35, &y_1^\prime &= 35^{-1} = 2 \quad\text{(in $\ZZ_3$)}, \\ y_2 &= 3 \cdot 7 = 21, &y_2^\prime &= 21^{-1} = 1 \quad\text{(in $\ZZ_5$)}, \\ y_3 &= 3 \cdot 5 = 15, &y_3^\prime &= 15^{-1} = 1 \quad\text{(in $\ZZ_7$)}. \end{align}$$ We now have $$\begin{align} x &= a_1 y_1 y_1^\prime + a_2 y_2 y_2^\prime + a_3 y_3 y_3^\prime \\ &= (1 \cdot 35 \cdot 2) + (4 \cdot 21 \cdot 1) + (6 \cdot 15 \cdot 1) \\ &= 70 + 84 + 90 \\ &= 244 = 34 \quad\text{(in $\ZZ_{105}$)}. \end{align}$$ Thus we also get the same result as the brute-force method.
Euler’s theorem
In this section, we will explore some shortcuts to compute remainders of numbers raised to very large powers. These will come in handy for public-key cryptosystems like RSA.
For \(n > 0\), define $$\phi(n) = \text{the number of integers in $\Set{0, \ldots, n-1}$ that are relatively prime to $n$}.$$
For example, \(\phi(11) = 10\) because all \(10\) positive numbers in \(\Set{0, \ldots, 10}\) are relatively prime to \(11\) except for \(0\), while \(\phi(12) = 4\) because only \(1\), \(5\), \(7\), and \(11\) are the only numbers in \(\Set{0, 1, \ldots, 11}\) that are relatively prime to \(12\). If \(p\) is prime, then \(\phi(p) = p-1\) since every positive number in \(\Set{0, \ldots, p-1}\) is relatively prime to \(p\).
If \(n\) and \(k\) are relatively prime, then $$k^{\phi(n)} \equiv 1 \pmod{n}.$$
If \(n\) happens to be a prime and since \(\phi(p) = p-1\) for prime \(p\), then we arrive at a special case called Fermat’s little theorem:
Suppose \(p\) is a prime and \(k\) is not a multiple of \(p\). Then $$k^{p-1} \equiv 1 \pmod{n}.$$
These theorems provide another way of computing inverses. Working in \(\ZZ_n\), we restate Euler’s theorem as:
If \(n\) and \(k\) are relatively prime, then $$k^{\phi(n)} = 1 \quad\text{(in $\ZZ_n$)}.$$
Dividing both sides by \(k\) (i.e., multiplying both sides by \(k^{-1}\)), we get $$k^{-1} = k^{\phi(n)} \cdot k^{-1} = k^{\phi(n)-1} \quad\text{(in $\ZZ_n$)}.$$ When \(n\) is prime, then it’s even more straightforward, as we only have $$k^{-1} = k^{(n-1)-1} = k^{n-2} \quad\text{(in $\ZZ_n$)}.$$
As before, suppose we want to find the inverse of \(18\) in \(\ZZ_{101}\). Since \(101\) is prime, we can just use the simpler formula: $$\begin{align} 18^{-1} &= 18^{101-2} \\ &= 18^{99} \\ &= 73 \quad\text{(in $\ZZ_{101}$)}. \end{align}$$
Computing Euler’s \(\phi\) function
RSA deals with arithmetic modulo the product of two large primes.4 So the following lemma shows how to compute \(\phi(pq)\) where \(p\) and \(q\) are distinct primes:
Now for the main result: the following theorem shows how to compute \(\phi(n)\) for any \(n\).
-
If \(p\) is a prime, then $$\phi\left(p^k\right) = p^k \left(1 - \frac{1}{p}\right) = p^k - p^{k-1}$$ for \(k \ge 1\).
-
If \(a\) and \(b\) are relatively prime, then \(\phi(ab) = \phi(a) \phi(b)\).
$$\begin{align} \phi(420) &= \phi(2^2 \cdot 3 \cdot 5 \cdot 7) \\ &= \phi(2^2) \cdot \phi(3) \cdot \phi(5) \cdot \phi(7) \\ &= \left(2^2 - 2^1\right) \left(3^1 - 3^0\right) \left(5^1 - 5^0\right) \left(7^1 - 7^0\right) \\ &= 96. \end{align}$$
The consequence of the main result is that we can compute \(\phi(n)\) using the prime factorization of \(n\):
For any number \(n\), if \(p_1, p_2, \cdots, p_k\) are the (distinct) prime factors of \(n\), then $$\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right).$$
We can also say \(a\) is a divisor of \(b\), or \(a\) is a factor of \(b\), or \(b\) is divisible by \(a\), or \(b\) is a multiple of \(a\). Take your pick.
We’ll formally define what rings are in the near future.
Finding an inverse “in \(\ZZ_n\)” is the same as finding an inverse “modulo \(n\).”
We call a number that is a product of two primes as semiprime.