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,   is the quotient.

divides        is divisor or factor of .

divides        .

does not divide        .

 Example  1.2 Since         divides        .  The quotient is .  We call  a divisor or factor of .

and        .

where

 Theorem 1.3 Let ,  and .   (a)  and        .   (b)  and        .   (c)        .

Proof

 Definition  1.4 is prime       if  then either  and  or  and .  is composite     is not a prime                    (   such that  and  and . )

 Example  1.5 only divisors are itself and        is prime.   and  divide        is composite.        *  and  are neither prime nor composite.
 Theorem  1.7 ,  is composite      has a divisor  satisfying .

 Algorithm  1.8 Testing Whether an Integer Is Prime This algorithm determines whether the integer  is prime. If  is prime, the algorithm returns . If  is composite, the algorithm returns a divisor  satisfying .  To test whether  divides , the algorithm checks whether the remainder when  is  divided by ,   is zero.         Input :        Output :
 Example  1.9 To determine whether  is prime, Algorithm 1.8 checks whether any of divides . Since none of these numbers divides , the condition is always false. Therefore, the algorithm returns  to indicate that  is prime.

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   is a common divisors of  and .   is the greatest  common divisors of  and .

 COROLLARY If ,  and  are integers, where , such that  and , then  whenever  and  are integers.

 Transitivity of Divisibility Prove that for all integers ,  and , if  and  then .

Proof

Show that

for some integer .

for some integer .

.

 Theorem  1.17 The prime factorizations of the positive integers  and  are , .  where each exponent is a nonnegative integer, and where all primes occurring in the    prime factorization of either  and  are included in both factorizations, with zero      exponents if necessary.  Then  is .

 Example  1.18

 Definition  1.19

 Example  1.20 is divisible by both  and .

 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

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 place place place 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 place place place place place Decimal Digit Symbol

The binary number system.

Example  2.1  Computer Representation of Integers

 Example  2.1 Computer Representation of Integers , . ,  express form ,      base  expansion of  where , , , ,  are non-negative integers less than , and .

The base  expansion of  is denoted by .

 Example  2.2 Binary to Decimal

 Algorithm  2.3 Converting an Integer from Base  to Decimal This algorithm returns the decimal value of the base  integer .       Input:  , ,      Output:  dec_val     base_b_to_dec (, , )         dec_val         power         for  to             dec_val  dec_val *power           power  power *           return dec_val

Algorithm  runs is time .

 Example  2.4 We show how Algorithm  converts the binary number  to decimal.

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 place place place 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 place place place place 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  into the base  integer .    The variable  is used as an index in the sequence .  The value of   is the remainder when  is divided by .  The value of  is the quotient when  is divided by .       Input:  ,      Output:  ,      dec_to_base_b(, , , )                 while ()

 Example  2.9 Decimal to Hexadecimal

 Example  2.10 Binary Addition Add the binary numbers  and .

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  and  and stores the sum in .       Input:  , ,      Output:       binary_addition(, , , )         carry         for  to

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

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 divided by . .        divided by . .  By inspection .  Therefore, .

 Theorem  3.2 If ,  , and   (), then .

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  and , where not both  and  are zero.       Input :   and (nonnegative integer, not both zero)     Output :  Greatest common divisor of  and   1.       2.       // make a largest  3.         4.        ()  5.      while  6.            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 , then there  such that .

 Example  3.8

● Computing  an Inverse Modulo an Integer

For  and  such that .

Find  such that .

is the inverse of .

 Example  3.11 Let  and .   and  where  and .  Thus, .  Here .  The inverse of  is .

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

http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm