An integer p > 1 is a prime number if and only if its only divisors2 are ;1 and ; p. Prime numbers play a critical role in number theory and in the techniques discussed in this chapter.

**PRIME NUMBERS**

A central concern of number theory is the study of prime
numbers. Indeed, whole books have been written on the subject
(e.g., [CRAN01], [RIBE96]). In this section, we provide an overview
relevant to the concerns of this book.

An integer *p *> 1 is a prime number if and only if its only divisors2 are ;1 and ; p.
Prime numbers play a critical role in number theory and in the techniques discussed in this chapter. Table 8.1 shows the primes less than 2000. Note the way
the primes are distributed. In particular, note the number of primes in each
range of 100 numbers.

Any integer *a *> 1 can be factored in
a unique way as

where *p*1 < *p*2 < ..... < *p**t *are
prime numbers and where each *a**i *is a positive integer. This is known as the fundamental theorem of arithmetic; a proof can be found in any text
on number theory.

91 = 7 * 13

3600 = 24 * 32 * 52

11011 = 7 * 112 * 13

It is useful for what follows to express this another way. If P is the set of all prime
numbers, then any positive integer *a *can be written uniquely in the following form:

The right-hand side is the product over all possible
prime numbers *p*; for any particular value of *a*, most of the exponents *a**p *will be 0.

The value of any given positive integer can be specified by simply listing all the nonzero exponents in the foregoing formulation.

**The ****integer 12 is represented by {***a*2 **= ****2, ***a*3 **= ****1}. **

**The ****integer 18 is represented by {***a*2 **= ****1, ***a*3 **= ****2}. **

**The ****integer 91 is represented by {***a*7 **= ****1, ***a*13 **= ****1}.**

*k *= 12 * 18 = (22 *
3) * (2
* 32) = 216

*k*2 = 2 + 1 = 3; *k*3 = 1 + 2 = 3

216 = 23 * 33 = 8 * 27

What does it mean, in terms of the prime factors of *a *and *b*, to say that *a *divides *b*â€™ Any integer of the form *p**n *can be divided only by
an integer that is of a lesser or equal
power of the same prime number, *p**j *with *j *â€¦ *n*. Thus,
we can say the following.

Given

*a ***= ****12; ***b ***= ****36; 12|36**

**12 ****= ****22 ***** ****3; 36 ****= ****22 ***** ****32**

*a***2 ****= ****2 ****= ***b***2**

*a***3 ****= ****1 ****â€¦ ****2 ****= ***b***3**

**Thus, the inequality
***a**p ***â€¦ ***b**p ***is satisfied for all prime numbers.**

It is easy to determine the greatest common
divisor3
of two positive integers
if we express each integer as the product
of primes.

**300 = 2****2 *****
****3****1 ***** ****5****2**

**18 = 2****1 ***** ****3****2**

**gcd(18, 300) = 21 ***** ****31 ***** ****50 ****= 6**

The following relationship always holds:

If *k *= gcd(*a*, *b*), then *k**p *= min(*a**p*, *b**p*) for all *p*.

Determining the prime factors of a large number is no easy
task, so the pre- ceding relationship does not directly lead to a practical
method of calculating the greatest common divisor.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : Asymmetric Ciphers : Introduction to Number Theory : Prime Numbers |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.