English | Español

# Try our Free Online Math Solver! Online Math Solver

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# 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