English | Español

Try our Free Online Math Solver!

Online Math Solver

 

 

 

 

 

 

 

 
 
 
 
 
 
 
 
 

 

 

 
 
 
 
 
 
 
 
 

Please use this form if you would like
to have this math solver on your website,
free of charge.


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 = 22 · 31 · 71

Using Standard Representation

• GCD and LCM

– we are given n and , where pi
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 = 22 · 3 · 7

– m = 63 = 32 · 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”}

Summary

• 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