Express Learning: Cryptography and Network Security

5

Number Theory

1. What are prime numbers and relatively prime numbers?

Ans.: Any positive integer greater than 1 is a prime number if and only if it is divisible by only two integers, 1 and itself. For example, the numbers 2, 3, 5, 7, 11, 13, 17 and 19 are all prime numbers, whereas the numbers 4, 6, 8 and 10 are composite (means not prime), because they have more than two divisors.

Two positive integers a and b are said to be relatively prime, or co-prime, if gcd(a, b)= 1. In other words, two numbers are said to be relatively prime if they have no common factors except the integer 1. For example, the integers 14 and 15 are relatively prime; however, the integers 14 and 16 are not relatively prime because they have a common factor other than ...