## Prime Numbers

A prime number can be divided, without a remainder, only by itself and by 1. For example, 19 can be divided only by 19 and by 1.

## Properties of Prime Numbers

•The only even prime number is 2. All other even numbers can be divided by 2.

•If the sum of a number’s digits is a multiple of 3, that number can be divided by 3.

•No prime number greater than 5 ends in a 5. Any number greater than 5 that ends in a 5 can be divided by 5.

•Zero and 1 are not considered prime numbers.

•Except for 0 and 1, a number is either a prime number or a composite number. A composite number is defined as any number, greater than 1, that is not prime.

## Prime Number List Till 100

Here are first few prime numbers

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, etc.

## Prime Number List Till 1000

List of Prime Number till 1000

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101 ,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197

199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431

433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039

## Methods to prove a number is a prime number

(A)The simplest way is to use Trial Division. Let N be the number in question to be tested. Divide by all prime numbers less than or equal to sqrt(N). If none go in evenly, then N is prime.

The number given is 1017

We can observer that 1031 lies between square of 30 and 33. So we can just keep trying till 33

a. 1031 is not divisible by 2

b. 1031 is not divisible by 3

c. 1031 is not divisible by 5

d. 1031 is not divisible by 7

e. 1031 is not divisible by 11

f. 1031 is not divisible by 13

g. 1031 is not divisible by 17

h. 1031 is not divisible by 19

i. 1031 is not divisible by 23

h. 1031 is not divisible by 29

j. 1031 is not divisible by 31

The next prime is 37. So we are done factoring. We can say 1031 is a Prime Number

(B) Here is a slightly more complicated way.

1) Pick any a with 1 < a < N-1.

2) Find the greatest common divisor d of a and N.

If d > 1, then N is composite, and d is a factor.

If d = 1, then compute the remainder of a^(N-1) when divided by N.

If this is not 1, then N is composite.

If this is 1, you can’t tell if N is prime or not.

Most composite numbers will be revealed to be composite by this method, This method is called the Fermat Test.

## Why Prime number are important and what is there uses

1) They are used in Cryptography. More specifically, some important cryptographic algorithms such as RSA critically depend on the fact that prime factorization of large numbers takes a long time. Basically you have a “public key” consisting of a product of two large primes used to encrypt a message, and a “secret key” consisting of the primes used to decrypt the message. You can make the public key public, and everyone can use it to encrypt messages to you, but only you know the prime factors and can decrypt the messages. Everyone else would have to factor the number, which takes too long to be practical, given the current state of the art of number theory. The two numbers, by the way, usually are 100 digits long or so, so factoring the product might require centuries on a large computer.

2) They are also used in hashing algorithm and sorting algorithm

## Prime Triplet

A prime triplet is a set of three prime numbers of the form (p, p + 2, p + 6) or (p, p + 4, p + 6).[1] With the exceptions of (2, 3, 5) and (3, 5, 7), this is the closest possible grouping of three prime numbers, since every third odd number greater than 3 is divisible by 3, and hence not prime.

The first prime triplets are

(5, 7, 11), (7, 11, 13), (11, 13, 17), (13, 17, 19), (17, 19, 23), (37, 41, 43), (41, 43, 47), (67, 71, 73), (97, 101, 103), (101, 103, 107), (103, 107, 109), (107, 109, 113), (191, 193, 197), (193, 197, 199), (223, 227, 229), (227, 229, 233), (277, 281, 283), (307, 311, 313), (311, 313, 317), (347, 349, 353), (457, 461, 463), (461, 463, 467), (613, 617, 619), (641, 643, 647), (821, 823, 827), (823, 827, 829), (853, 857, 859), (857, 859, 863), (877, 881, 883), (881, 883, 887)

A prime triplet contains a pair of twin primes (p and p + 2, or p + 4 and p + 6), a pair of cousin primes (p and p + 4, or p + 2 and p + 6), and a pair of sexy primes (p and p + 6).

A prime can be a member of up to three prime triplets – for example, 103 is a member of (97, 101, 103), (101, 103, 107) and (103, 107, 109). When this happens, the five involved primes form a prime quintuplet.

## Co-prime

In mathematics, two integers a and b are said to be coprime (also spelled co-prime) or relatively prime if they have no common positive divisor other than 1 or, equivalently, if their greatest common divisor is 1.

For example, 14 and 15 are coprime, being commonly divisible by only 1, but 14 and 21 are not, because they are both divisible by 7

**Related Links**

prime factorization of 100

Table of Factors

factors of 35