# Introduction to Number Theory

**Extended Euclidean Algorithm
**

– algorithm steps :

– thus, we get

• Also, if gcd(a, b) = 1, then ax+by = 1, i.e., ax mod b = 1

• **Input:** integers a ≥ b > 0

• **Output:** g = gcd(a, b) and x and y with ax+by = gcd(a, b)

• The **algorithm** itself:

x = 1; y = 0; g = a; r = 0; x = 1; t = b

while (t > 0) {

q = [g/t]

u = x − qr; v = y − qs; w = g − qt

x = r; y = s; g = t

r = u; s = v; t = w

}

• **Algorithm invariants:** ax+by = g and ar +bs = t

• ** Complexity ** of the algorithm (theorem)

– this result is due to , 1845

– the number of steps ( division operations ) needed by the Euclidean

algorithm is no more than five times of decimal digits in the smaller

of the two numbers

**• Corollary**

– the number of bit operations needed by the Euclidean algorithm is

, where a is the larger of the two numbers

**Prime and Composite Numbers**

**• Prime numbers**

– a prime number is an integer greater than 1 which is divisible by 1

and itself

– the first prime numbers are 2, 3, 5, 7, 11, 13, 17, etc.

**• Composite numbers**

– a composite number is an integer greater than 1 which is not prime

– the composite numbers are 4, 6, 8, 9, 10, 12, 14, etc.

**• Relatively prime numbers**

– integers a and b are relatively prime is gcd(a, b) = 1

– relatively prime numbers don’t have common divisors other than 1

**Decomposition of numbers**

• **Fundamental Theorem of Arithmetics :**

– every integer n > 1 can be written as a product of prime numbers

– and this product is unique if the primes are written in

non- decreasing order

– here are the primes
that divide n and is the

number of factors of dividing n

– this decomposition is called the **standard representation**

• **Example:** 84 = 2 · 2 · 3 · 7 = 2^{2} · 3^{1} · 7^{1}

**Using Standard Representation**

**• GCD and LCM **

– we are given n and
, where p_{i}

are prime numbers and

–

– the** least common multiple **of integers a and b is the smaller positive

integer divisible by both a and b

–

– also, gcd(a, b) · lcm(a, b) = ab

**• Examples:**

– n = 84 = 2^{2} · 3 · 7

– m = 63 = 3^{2} · 7

– gcd(84, 63) =

– lcm(84, 63) =

– gcd(84, 63) · lcm(84, 63) =

**Distribution Distribution of prime numbers**

• In cryptography, we’ll need to use large primes and
would like to know

how prime numbers are distributed

• (Theorem) The number of prime numbers is **infinite**

• (Theorem)** Gaps between primes**

– for every positive integer n, there are n or more consecutive

composite numbers

• For a positive real number x, let π(x) be the number of prime numbers

≤
x

**• The Prime Number Theorem**

– π(x) tends to x/ ln x as x goes to infinity. In symbols ,

– this tells us that there are plenty of large primes

• The question now is how we find prime numbers

**• Theorem**

– if integer n > 1 is composite, it has a prime divisor

– in other words, if n > 1 has no prime divisor
, then it is

prime

**Finding Primes**

• This suggests a simple** algorithm for testing a small
number for
primality** (and factoring if it is composite)

– Input: a positive integer n

– Output: whether n is prime, or one or more factors of n

m = n; p = 2

while

if (m mod p = 0) {

print “n is composite with factor p”; m = m/p

}

else { p = p+1 }

}

if (m = n) { print “n is prime” }

else if (m > 1) { print “the last factor of n is m”}

**• Today we’ve learned:**

– divisibility theorems

– how to use Euclidean algorithm to compute GCD and more

– the number of prime numbers is large and they are well distributed

**• More on number theory is still ahead**

Prev | Next |