Chapter 5 Introduction to Number Theory
[References]
1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson
5 Introduction to Number Theory
5.1 Divisors
5.2 Representations of Integers and Integer Algorithms
5.3 The Euclidean Algorithm
5.4 The RSA Public-Key Cryptosystem (Skipped)
5.1 Divisors
|
Definition 1.1 |
|
|
|
|
divides 
is divisor or factor of 
.
divides 
.
does not divide 
.
|
Example 1.2 |
|
|
Since The quotient is |
|
, 
and 
.
where 
|
Theorem 1.3 |
|
|
Let (a) (b) (c) |
|
Proof
|
Definition 1.4 |
|
|
(
|
|
|
Example 1.5 |
|
|
* |
|
|
Theorem 1.7 |
|
|
|
|
|
Algorithm 1.8 |
Testing Whether an Integer Is Prime |
|
This algorithm determines whether the integer If If To test whether Input : Output : |
|
|
Example 1.9 |
|
|
To determine whether
divides
is always false. Therefore, the algorithm returns |
|
Fundamental Theorem of Arithmetic or the unique factorization theorem.
Except for the order of the prime factors, the prime factors are unique.
|
Theorem 1.11 |
Fundamental Theorem of Arithmetic |
|
|
|
|
Theorem 1.12 |
|
|
There are infinitely many prime numbers. |
|
Proof
|
Definition 1.14 |
|
|
|
|
|
Example 1.15 |
|
|
|
|
|
Example 1.16 |
|
|
Find Using prime factorization
|
|
|
COROLLARY |
|
|
If |
|
|
Transitivity of Divisibility |
|
|
Prove that for all integers |
|
Proof
Show that 
for some integer 
.
for some integer 
.
. 
|
Theorem 1.17 |
|
|
The prime factorizations of the positive integers
where each exponent is a nonnegative integer, and where all primes occurring in the prime factorization of either Then
|
|
|
Example 1.18 |
|
|
|
|
|
Definition 1.19 |
|
|
|
|
|
Example 1.20 |
|
|
|
|
|
Example 1.21 |
|
|
|
|
|
Theorem 1.22 |
|
|
|
|
|
Example 1.23 |
|
|
|
|
|
Example 1.24 |
|
|
|
|
|
Theorem 1.25 |
|
|
|
|
Exercises 11, 24, 29, 31
5.2 Representations of Integers and Integer Algorithms
A bit is a binary digit. A bit has a 
and a 
.
The binary Number System consists of 
symbols(bit).
The octal Number System consists of 
symbols.
The decimal Number System consists of 
symbols.
The hexadecimal Number System consists of 
symbols.
The system is based the base of the number system.
Decimal Number System
Integer form is
based 
where 
and each 
is one of the decimal digits 
, 
,
, 
, 
, 
, 
, 
, 
, 
.
|
Place |
|
|
|
|
|
Decimal Digit |
|
|
|
|
|
Symbol |
|
|
|
|
The decimal number system.
Binary Number System
Integer form is
based 
where each 
and each 
is one of the binary digits 
, 
.
|
Place |
|
|
|
|
|
|
Decimal Digit |
|
|
|
|
|
|
Symbol |
|
|
|
|
|
The binary number system.
Example 2.1 Computer Representation of Integers
|
Example 2.1 |
Computer Representation of Integers |
|
where |
|
The base 
expansion of 
is denoted by 
.
|
Example 2.2 |
Binary to Decimal |
|
|
|
|
Algorithm 2.3 |
Converting an Integer from Base |
|
This algorithm returns the decimal value of the base Input: Output: dec_val base_b_to_dec ( dec_val power for dec_val power return dec_val |
|
Algorithm 
runs is time 
.
|
Example 2.4 |
|
|
We show how Algorithm |
|
Solution
Here 
, 
and
, 
, 
, 
.
First, 
is set to 
, and power is set to 
.
We then enter the for loop.
Since 
and 
,
* 
*
.
Thus 
becomes 
. Executing
* 
sets 
to 
. We return to the top of the for loop.
Since 
and 
,
* 
*
.
Thus 
becomes 
. Executing
* 
sets 
to 
.
We return to the top of the for loop.
Since 
and 
,
* 
*
.
Thus 
becomes 
. Executing
* 
sets 
to 
.
We return to the top of the for loop.
Since 
and 
,
* 
*
.
Thus 
becomes 
. Executing
* 
sets 
to 
.
The for loop terminates and the algorithm returns 
, the decimal value of the binary number 
. 
● Octal number system
Integer form is
based 
where 
and each 
is one of the octal digits 
, 
,
, 
, 
, 
, 
, 
.
|
Place |
|
|
|
|
|
Decimal Digit |
|
|
|
|
|
Symbol |
|
|
|
|
The octal number system.
● Hexadecimal number system
Integer form is
based 
where 
and each 
is one of the hexadecimal digits 
, 
,
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
, 
.
|
Place |
|
|
|
|
|
|
Decimal Digit |
|
|
|
|
|
|
Symbol |
|
|
|
|
|
The hexadecimal number system.
|
Example 2.5 |
Hexadecimal to Decimal |
|
|
|
|
Example 2.6 |
Decimal to Binary |
|
|
|
|
Algorithm 2.7 |
Converting a Decimal Integer into Base |
|
This algorithm convert the positive integer The value of The value of Input: Output: dec_to_base_b( while ( |
|
|
Example 2.9 |
Decimal to Hexadecimal |
|
|
|
● Addition Binary Number, Binary addition table
|
|
|
|
|
|
|
Example 2.10 |
Binary Addition |
|
Add the binary numbers |
|
Solution
We begin from the right, adding 
and 
. This sum is 
.
We write 
and carry 
. At this point the computation is
Next, we add 
and 
and 
. This sum is 
.
We write 
and carry 
. At this point the computation is
Continuing in this way, we obtain
|
Algorithm 2.12 |
Adding Binary Numbers |
|
This algorithm add the binary numbers Input: Output: binary_addition( carry for |
|
|
Example 2.13 |
Hexadecimal Addition |
|
Add the hexadecimal numbers |
|
Solution
We begin from the right, adding 
and 
. This sum is 
.
We write 
. At this point the computation is
Next, we add 
and 
. This sum is 
.
We write 
and carry 
. At this point the computation is
Continuing in this way, we obtain
The straightforward way to compute this power is to repeatedly multiply by 
’s
which uses 
multiplications. We can do better using repeated squaring.
Compute 
.
uses 
multiplication
uses 
addition multiplication
uses 
addition multiplication
uses 
addition multiplication
uses 
addition multiplication
The expansion of 
is power of 
, that is the binary expansion, is
.
We can compute 
as
which 
additional multiplications for a total of 
multiplications.
The straightforward technique uses 
multiplication. 
|
Example 2.15 |
Binary representation of the exponent |
|
|
|
For example 
|
Theorem 2.17 |
|
|
|
|
|
Example 2.18 |
|
|
|
|
Exercises 31, 38, 56, 59
5.3 The Euclidean Algorithm
Euclidean Algorithm is algorithm for finding the greatest common divisor of two integers.
The Euclidean Algorithm
Let 
, where 
, 
, 
and 
are integers. Then 
.
|
Example 3.1 |
|
|
By inspection Therefore,
|
|
|
Theorem 3.2 |
|
|
If
|
|
Proof
The common divisors of 
and 
are the same as the common divisors of 
and 
.
Show that 
. 
We have the same greatest common divisor.
divides both 
and 
.
divides 
.
Any common divisor of 
and 
is a common divisor of 
and 
.
divides both 
and 
.
divides 
.
Any common divisor of 
and 
is a common divisor of 
and 
.
Hence, 
. 
|
Algorithm 3.3 |
Euclidean Algorithm |
|
This algorithm finds the greatest common divisor of the nonnegative integer Input : Output : Greatest common divisor of 1. 2. // make a largest 3. 4. ( 5. while
7. 8. 9. 10. return 11. |
|
ÉTIENNE BÉZOUT (1730–1783) Reading the writings of the great mathematician Leonhard Euler enticed him to become a mathematician. In 1758 he was appointed to a position at the Académie des Sciences in Paris. Bézout is also credited with inventing the determinant.
|
Theorem 3.7 |
BÉZOUT’'S THEOREM |
|
If and
|
|
|
Example 3.8 |
|
|
|
|
● Computing an Inverse Modulo an Integer
For 
, 
and 
such that 
.
Find 
, 
such that 
.
is the inverse of 
.
|
Example 3.11 |
|
|
Let Thus,
Here The inverse of |
|
Exercises 4, 11, 36
5.4 The RSA Public-Key Cryptosystem (Skip)
Q & A
Exercises 1, 4, 8, 11, 14, 16, 19, 25 [End of Ch. 3]
Copyright by SGLee, SKKU sglee@skku.edu
Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).
, 
.
, 
divides 
.
is 
is the 
divides 
.
. We call 
a 
.
,
.
.
.
.
is
.
is
. )
only divisors are itself and
and
,
.
is prime.
is prime, the algorithm returns 
.
is composite,
satisfying 
.
divides 
, the algorithm checks whether the remainder when 
is divided by 
, 
is zero.
. Since none of these numbers divides
, the condition
is a common divisors of 
and 
.
is the greatest common divisors of 
and 
. 
,
, such that
, then
,
, if
.
,
.
.
is divisible by both
.
place
place
place
place
place
place
place
place
place
, 
. 
, 
express form
, 
expansion of 
, 
, 
, 
, 
are non-negative integers less than 
, and 
.
to Decimal
integer 
.
, 
, 
, 
, 
) 
to 
dec_val 
*power
power * 
converts the binary number 
to decimal.
place
place
place
place
place
place
place
place
place
into the base 
integer 
. The variable 
is used as an index in the sequence 
.
is the remainder when 
is divided by 
.
is the quotient when 
is divided by 
.
, 
, 
, 
, 
, 
) 
)
.
.
,
,
,
,
,
)
.
divided by 
.
.
divided by 
.
.
.
.
, 
, and 
(
), then
.
and 
, where not both 
and 
are zero.
and 
(nonnegative integer, not both zero)
and 
)
6. 
, then there 
such that
.
and 
.
and 
where 
and 
.
.
.
is 
.