## 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 ...

Get *Express Learning: Cryptography and Network Security* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.