Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3.1 Basic Notions

3.1.1 Divisibility

Number theory is concerned with the properties of the integers. One of the most important is divisibility.

Definition

Let $a$ $a$ and $b$ $b$ be integers with $a \neq 0 .$ $a \neq 0 .$ We say that $a$ $a$ divides $b,$ $b,$ if there is an integer $k$ $k$ such that $b = a k .$ $b = a k .$ This is denoted by $a | b .$ $a | b .$ Another way to express this is that $b$ $b$ is a multiple of $a .$ $a .$

Example

$3 | 15,$ $3 | 15,$ $- 15 | 60,$ $- 15 | 60,$ $7 ∤ 18$ $7 ∤ 18$ (does not divide).

The following properties of divisibility are useful.

Proposition

Let $a, b, c$ $a, b, c$ represent integers.

For every $a \neq 0,$ $a \neq 0,$ $a | 0$ $a | 0$ and $a | a .$ $a | a .$ Also, $1 | b$ $1 | b$ for every $b .$ $b .$
If $a | b$ $a | b$ and $b | c,$ $b | c,$ then $a | c .$ $a | c .$
If $a | b$ $a | b$ and $a | c,$ $a | c,$ then $a | (s b + t c)$ $a | (s b + t c)$ for all integers $s$ $s$ and $t .$ $t .$

Proof. Since $0 = a \cdot 0,$ $0 = a \cdot 0,$ we may take $k = 0$ $k = 0$ in the definition to obtain $a | 0 .$ $a | 0 .$ Since $a = a \cdot 1,$ $a = a \cdot 1,$ we take $k = 1$ $k = 1$ to prove $a | a .$ $a | a .$ Since $b = 1 \cdot b,$ $b = 1 \cdot b,$ we have $1 | b .$ $1 | b .$ This proves (1). In (2), there exist $k$ $k$ and $ℓ$ $ℓ$ such that $b = a k$ $b = a k$ and $c = b ℓ .$ $c = b ℓ .$ Therefore, $c = (k ℓ) a,$ $c = (k ℓ) a,$ so $a | c .$ $a | c .$ For (3), write $b = a k_{1}$ $b = a k_{1}$ and $c = a k_{2} .$ $c = a k_{2} .$ Then $s b + t c = a (s k_{1} + t k_{2}),$ $s b + t c = a (s k_{1} + t k_{2}),$ so $a | s b + t c .$ $a | s b + t c .$

For example, take $a = 2$ $a = 2$ in part (2). Then $2 | b$ $2 | b$ simply means that $b$ $b$ is even. The statement in the proposition says that $c,$ $c,$ which is a multiple of the even number $b,$ $b,$ must also be even (that is, a multiple of $a = 2$ $a = 2$ ).

3.1.2 Prime Numbers

A number $p > 1$ $p > 1$ whose positive divisors are only 1 and itself is called a prime number. The first few primes are $2, 3, 5, 7, 11, 13, 17, \dots .$ $2, 3, 5, 7, 11, 13, 17, \dots .$ An integer $n > 1$ $n > 1$ that is not prime is called composite, which means that $n$ $n$ must be expressible as a product $a b$ $a b$ of integers with $1 < a, b < n .$ $1 < a, b < n .$ A fact, known already to Euclid, is that there are infinitely many prime numbers. A more precise statement is the following, proved in 1896.

Prime Number Theorem

Let $π (x)$ $π (x)$ be the number of primes less than $x .$ $x .$ Then

π (x) \approx \frac{x}{\ln x},

$π (x) \approx \frac{x}{\ln x},$

in the sense that the ratio $π (x) / (x / ln x) \to 1$ $π (x) / (x / ln x) \to 1$ as $x \to ∞ .$ $x \to ∞ .$

We won’t prove this here; its proof would lead us too far away from our cryptographic goals. In various applications, we’ll need large primes, say of around 300 digits. We can estimate the number of 300-digit primes as follows:

π (10^{300}) - π (10^{299}) \approx \frac{10^{300}}{ln 10^{300}} - \frac{10^{299}}{ln 10^{299}} \approx 1.4 \times 10^{297} .

$π (10^{300}) - π (10^{299}) \approx \frac{10^{300}}{ln 10^{300}} - \frac{10^{299}}{ln 10^{299}} \approx 1.4 \times 10^{297} .$

So there are certainly enough such primes. Later, we’ll discuss how to find them.

Prime numbers are the building blocks of the integers. Every positive integer has a unique representation as a product of prime numbers raised to different powers. For example, 504 and 1125 have the following factorizations:

504 = 2^{3} 3^{2} 7, 1125 = 3^{2} 5^{3} .

$504 = 2^{3} 3^{2} 7, 1125 = 3^{2} 5^{3} .$

Moreover, these factorizations are unique, except for reordering the factors. For example, if we factor 504 into primes, then we will always obtain three factors of 2, two factors of 3, and one factor of 7. Anyone who obtains the prime 41 as a factor has made a mistake.

Theorem

Every positive integer is a product of primes. This factorization into primes is unique, up to reordering the factors.

Proof. There is a small technicality that must be dealt with before we begin. When dealing with products, it is convenient to make the convention that an empty product equals 1. This is similar to the convention that $x^{0} = 1 .$ $x^{0} = 1 .$ Therefore, the positive integer 1 is a product of primes, namely the empty product. Also, each prime is regarded as a one-factor product of primes.

Suppose there exist positive integers that are not products of primes. Let $n$ $n$ be the smallest such integer. Then $n$ $n$ cannot be 1 ( $=$ $=$ the empty product), or a prime ( $=$ $=$ a one-factor product), so $n$ $n$ must be composite. Therefore, $n = a b$ $n = a b$ with $1 < a, b < n .$ $1 < a, b < n .$ Since $n$ $n$ is the smallest positive integer that is not a product of primes, both $a$ $a$ and $b$ $b$ are products of primes. But a product of primes times a product of primes is a product of primes, so $n = a b$ $n = a b$ is a product of primes. This contradiction shows that the set of integers that are not products of primes must be the empty set. Therefore, every positive integer is a product of primes.

The uniqueness of the factorization is more difficult to prove. We need the following very important property of primes.

Lemma

If $p$ $p$ is a prime and $p$ $p$ divides a product of integers $a b,$ $a b,$ then either $p | a$ $p | a$ or $p | b .$ $p | b .$ More generally, if a prime $p$ $p$ divides a product $a b \dots z,$ $a b \dots z,$ then $p$ $p$ must divide one of the factors $a, b, \dots, z .$ $a, b, \dots, z .$

For example, when $p = 2,$ $p = 2,$ this says that if a product of two integers is even then one of the two integers must be even. The proof of the lemma will be given at the end of the next section, after we discuss the Extended Euclidean algorithm.

Continuing with the proof of the theorem, suppose that an integer $n$ $n$ can be written as a product of primes in two different ways:

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{s}^{a_{s}} = q_{1}^{b_{1}} q_{2}^{b_{2}} \dots q_{t}^{b_{t}},

$n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{s}^{a_{s}} = q_{1}^{b_{1}} q_{2}^{b_{2}} \dots q_{t}^{b_{t}},$

where $p_{1}, \dots, p_{s}$ $p_{1}, \dots, p_{s}$ and $q_{1}, \dots, q_{t}$ $q_{1}, \dots, q_{t}$ are primes, and the exponents $a_{i}$ $a_{i}$ and $b_{j}$ $b_{j}$ are nonzero. If a prime occurs in both factorizations, divide both sides by it to obtain a shorter relation. Continuing in this way, we may assume that none of the primes $p_{1}, \dots, p_{s}$ $p_{1}, \dots, p_{s}$ occur among the $q_{j}$ $q_{j}$ ’s. Take a prime that occurs on the left side, say $p_{1} .$ $p_{1} .$ Since $p_{1}$ $p_{1}$ divides $n,$ $n,$ which equals $q_{1} q_{1} \dots q_{1} q_{2} q_{2} c d o t s q_{t} q_{t},$ $q_{1} q_{1} \dots q_{1} q_{2} q_{2} c d o t s q_{t} q_{t},$ the lemma says that $p_{1}$ $p_{1}$ must divide one of the factors $q_{j} .$ $q_{j} .$ Since $q_{j}$ $q_{j}$ is prime, $p_{1} = q_{j} .$ $p_{1} = q_{j} .$ This contradicts the assumption that $p_{1}$ $p_{1}$ does not occur among the $q_{j}$ $q_{j}$ ’s. Therefore, an integer cannot have two distinct factorizations, as claimed.

3.1.3 Greatest Common Divisor

The greatest common divisor of $a$ $a$ and $b$ $b$ is the largest positive integer dividing both $a$ $a$ and $b$ $b$ and is denoted by either $g c d (a, b)$ $g c d (a, b)$ or by $(a, b) .$ $(a, b) .$ In this book, we use the first notation. To avoid technicalities, we always assume implicitly that at least one of $a$ $a$ and $b$ $b$ is nonzero.

Example

$gcd (6, 4) = 2, gcd (5, 7) = 1, gcd (24, 60) = 12 .$ $gcd (6, 4) = 2, gcd (5, 7) = 1, gcd (24, 60) = 12 .$

We say that $a$ $a$ and $b$ $b$ are relatively prime if $gcd (a, b) = 1 .$ $gcd (a, b) = 1 .$ There are two standard ways for finding the gcd:

If you can factor $a$ $a$ and $b$ $b$ into primes, do so. For each prime number, look at the powers that it appears in the factorizations of $a$ $a$ and $b .$ $b .$ Take the smaller of the two. Put these prime powers together to get the gcd. This is easiest to understand by examples:

$\begin{array}{l} 576 = 2^{6} 3^{2}, 135 = 3^{3} 5, \gcd (576, 135) = 3^{2} = 9 \\ \gcd (2^{5} 3^{4} 7^{2}, 2^{2} 5^{3} 7) = 2^{2} 3^{0} 5^{0} 7^{1} = 2^{2} 7 = 28. \end{array}$ $\begin{array}{l} 576 = 2^{6} 3^{2}, 135 = 3^{3} 5, \gcd (576, 135) = 3^{2} = 9 \\ \gcd (2^{5} 3^{4} 7^{2}, 2^{2} 5^{3} 7) = 2^{2} 3^{0} 5^{0} 7^{1} = 2^{2} 7 = 28. \end{array}$

Note that if a prime does not appear in a factorization, then it cannot appear in the gcd.
Suppose $a$ $a$ and $b$ $b$ are large numbers, so it might not be easy to factor them. The gcd can be calculated by a procedure known as the Euclidean algorithm. It goes back to what everyone learned in grade school: division with remainder. Before giving a formal description of the algorithm, let’s see some examples.

Example

Compute gcd(482, 1180).

SOLUTION

Divide 482 into 1180. The quotient is 2 and the remainder is 216. Now divide the remainder 216 into 482. The quotient is 2 and the remainder is 50. Divide the remainder 50 into the previous remainder 216. The quotient is 4 and the remainder is 16. Continue this process of dividing the most recent remainder into the previous one. The last nonzero remainder is the gcd, which is 2 in this case:

\begin{array}{l} 1180 & = & 2 \cdot 482 + 216 \\ 482 & = & 2 \cdot 216 + 50 \\ 216 & = & 4 \cdot 50 + 16 \\ 50 & = & 3 \cdot 16 + 2 \\ 16 & = & 8 \cdot 2 + 0. \end{array}

$\begin{array}{l} 1180 & = & 2 \cdot 482 + 216 \\ 482 & = & 2 \cdot 216 + 50 \\ 216 & = & 4 \cdot 50 + 16 \\ 50 & = & 3 \cdot 16 + 2 \\ 16 & = & 8 \cdot 2 + 0. \end{array}$

Notice how the numbers are shifted:

remainder \to todivisor \to todividend \to toignore .

$remainder \to todivisor \to todividend \to toignore .$

Here is another example:

\begin{array}{l} 12345 & = & 1 \cdot 11111 + 1234 \\ 11111 & = & 9 \cdot 1234 + 5 \\ 1234 & = & 246 \cdot 5 + 4 \\ 5 & = & 1 \cdot 4 + 1 \\ 4 & = & 4 \cdot 1 + 0. \end{array}

$\begin{array}{l} 12345 & = & 1 \cdot 11111 + 1234 \\ 11111 & = & 9 \cdot 1234 + 5 \\ 1234 & = & 246 \cdot 5 + 4 \\ 5 & = & 1 \cdot 4 + 1 \\ 4 & = & 4 \cdot 1 + 0. \end{array}$

Therefore, $gcd (12345, 11111) = 1 .$ $gcd (12345, 11111) = 1 .$

Using these examples as guidelines, we can now give a more formal description of the Euclidean algorithm. Suppose that $a$ $a$ is greater than $b .$ $b .$ If not, switch $a$ $a$ and $b .$ $b .$ The first step is to divide $a$ $a$ by $b,$ $b,$ hence represent $a$ $a$ in the form

a = q_{1} b + r_{1} .

$a = q_{1} b + r_{1} .$

If $r_{1} = 0,$ $r_{1} = 0,$ then $b$ $b$ divides $a$ $a$ and the greatest common divisor is $b .$ $b .$ If $r_{1} \neq 0,$ $r_{1} \neq 0,$ then continue by representing $b$ $b$ in the form

b = q_{2} r_{1} + r_{2} .

$b = q_{2} r_{1} + r_{2} .$

Continue in this way until the remainder is zero, giving the following sequence of steps:

\begin{array}{l} a & = & q_{1} b + r_{1} \\ b & = & q_{2} r_{1} + r_{2} \\ r_{1} & = & q_{3} r_{2} + r_{3} \\ ⋮ & ⋮ & ⋮ \\ r_{k - 2} & = & q_{k} r_{k - 1} + r_{k} \\ r_{k - 1} & = & q_{k + 1} r_{k} . \end{array}

$\begin{array}{l} a & = & q_{1} b + r_{1} \\ b & = & q_{2} r_{1} + r_{2} \\ r_{1} & = & q_{3} r_{2} + r_{3} \\ ⋮ & ⋮ & ⋮ \\ r_{k - 2} & = & q_{k} r_{k - 1} + r_{k} \\ r_{k - 1} & = & q_{k + 1} r_{k} . \end{array}$

The conclusion is that

gcd (a, b) = r_{k} .

$gcd (a, b) = r_{k} .$

There are two important aspects to this algorithm:

It does not require factorization of the numbers.
It is fast.

For a proof that it actually computes the gcd, see Exercise 59.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.1 Basic Notions

Create new playlist

Sign In

Sign Up

Table of Contents for
3.1 Basic Notions