Cryptography: Number Theory - Euclidean Algorithm

Euclidean Algorithm 

•One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers.

•Relative Prime

•Two integers are relatively prime if their only common positive integer factor is 1.

Relatively Prime Integers 
Definition:

Two integers a and b are relatively prime if gcd(a, b) = 1.

Examples:

•Are 15 and 28 relatively prime?

–Yes, gcd(15, 28) = 1.

•Are 55 and 28 relatively prime?

–Yes, gcd(55, 28) = 1.

•Are 35 and 28 relatively prime?

–No, gcd(35, 28) = 7.

 

Greatest Common Divisor  

•Let a and b be integers, not both zero.

•The largest integer d such that d | a and d | b is called the greatest common divisor of a and b.

•The greatest common divisor of a and b is denoted by gcd(a, b).

•

•Example 1: What is gcd(48, 72) ?

–The positive common divisors of 48 and 72 are
1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24.

•Example 2: What is gcd(19, 72) ?

–The only positive common divisor of 19 and 72 is
1, so gcd(19, 72) = 1.