# Prime Numbers

A ** prime number** is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 5 is a prime number because its only factors are 1 and 5. In other words, \(5 = 1\times 5 \) and 5 cannot be written as a product of any other numbers; therefore, 5 is prime.

Some more examples of prime numbers are \(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,........ \)

In contrast to prime numbers, a **composite number** is a positive integer greater than 1 that has more than 2 positive divisors. For example, 4 is a composite number because it has 3 positive divisors: 1, 2, and 4. In other words, 4 can be written as a product of more than one pair of positive integers: \( 4 = 1 \times 4 \) AND \( 4 = 2 \times 2 \).

All positive integers greater than one are either prime or composite.

Some additional facts about primes:

- There are infinitely many prime numbers.
- There is only one even prime number: 2.
- For every \(n,\) between every \(n\) and \(2n\), there is at least one prime.
- There are \(168\) primes between \(1\) and \(1000\).
- The largest prime number found so far is \(2^{74,207,281}-1\), a number with more than 22,000,000 digits.

#### Contents

## Identifying Prime Numbers

In general, identifying prime numbers is a very difficult problem. This, along with integer factorisation, has no algorithm in polynomial time. In fact, it is so challenging that much of computer cryptography is built around the fact that there is no known computationally feasible way to find the factors of a large number.

However, it is quite simple to check whether or not smaller numbers are primes by using a table of prime numbers, divisibility rules, or by checking all possible divisors manually.

In the following sequence, how many prime numbers are present?

\[121,12321,1234321,123454321,\ldots\]

We have

\[\begin{align} 121&= 11×11\\ 12321&= 111×111\\ 1234321&= 1111×1111\\ 123454321&= 11111×11111. \end{align}\]

So,

nonumbers in the given sequence are prime numbers. \(_\square\)

How many numbers in the following sequence are prime numbers?

\[101,10201,102030201,1020304030201, \ldots\]

We have the following factorization:

- \(101\) has no factors other than 1 and itself. So, it is a prime number.
- \(10201 = 101×101\)
- \(102030201 = 10101×10101\)
- \(1020304030201 = 1010101×1010101\)
So, there is only \(1\) prime number in the given sequence. \(_\square\)

## What is the next prime number after 11?

After 11, we can see that 12 is divisible by \(1,2,3,4,6,12\), and thus it is not prime. However, 13 is not divisible by any number other than itself and 1.

Thus, 13 is the next prime number after 11. \(_\square\)

What is the sum of the largest two 2-digit prime numbers?

Counting backward,

- we get to know that \(99\) is divisible by \(3\);
- then \(98\) is divisible by \(2\);
- then, \(97\) is divisible only by 1 and itself, implying it is the largest 2-digit prime number;
- then, \(96\) is divisible by \(2\);
- then, \(95\) is divisible by \(5\);
- then, \(94\) is divisible by \(2\);
- then, \(93\) is divisible by \(3\);
- then, \(92\) is divisible by \(2\);
- then, \(91\) is divisible by \(7\);
- then, \(90\) is divisible by \(2\);
- then \(89\) is divisible by only 1 and itself, implying it is the second largest 2-digit prime number.
So, the required answer is \(97+89=186.\) \(_\square\)

Which prime number follows \(1997\)?

\(1998\) is divisible by \(2\).

\(1999\) is divisible by only 1 and itself.

So, the prime number which follows 1997 is \(1999\). \(_\square\)

Find the sum of all prime numbers below \(100\).

We have

\[\begin{align} &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 \\ = &1060. \ _\square \end{align}\]

What is the largest 3-digit prime number?

Counting backward, we have the following:

- \(999\) is the largest 3-digit number, but as it is divisible by \(3\), it is not prime.
- \(998\) is the second largest 3-digit number, but as it is divisible by \(2\), it is not prime.
- \(997\) is the third largest 3-digit number and it has no other factors other than 1 and itself. So, \(997\) is the largest 3-digit prime number. \(_\square\)

## List the first three 2-digit prime numbers.

The first three 2-digit prime numbers are 11, 13, and 17. \(_\square\)

## Example Problems involving Prime Numbers

## \(n\) is the greatest prime number less than 50, and \(m\) is the least prime number greater than 50. What is the value of \(n+m?\)

Let's work backward for \(n\).

\(49\) is divisible by \(7\), and from the property of primes it is enough information to conclude that the number is not prime.

\(48\) is divisible by \(2,\) so cancel it.

When we look at \(47,\) it doesn't have any divisor other than one and itself. So it is indeed a prime: \(n=47.\)We use the same process in looking for \(m\).

\(51\) is divisible by \(3\).

\(52\) is divisible by \(2\).

\(53\) doesn't have any other divisor other than one and itself, so it is indeed a prime: \(m=53.\)Therefore, \[n+m=100.\ _\square\]

## Consider the expression \(2^{n}-1,\) where \(n\) is an integer greater than \(1.\) What are the least two values of \(n\) for which the expression doesn't produce a prime number?

Let's check by plugging in numbers in increasing order.

- \(2^{2}-1=3\) is prime.
- \(2^{3}-1=7\) is prime.
- \(2^{4}-1=15\), which is divisible by 3, so it isn't prime.
- \(2^{5}-1=31\) is prime.
- \(2^{6}-1=63\), which is divisible by 7, so it isn't prime.
Therefore, the least two values of \(n\) are 4 and 6. \(_\square\)

## Let \(p\) be a prime number greater than \(3\). Prove that \((p-1)(p+1)\) is always divisible by \(6\).

Any integer can be written in the form \(6k+n,0 \le n\le5\).

\(6k\) cannot be a prime.

\(6k+1\) may be a prime.

\(6k+2\) cannot be a prime.

\(6k+3\) cannot be a prime.

\(6k+4\) cannot be a prime.

\(6k+5\) may be a prime.

Thus, any prime \(p \ge3\) can be represented in the form \(6k+5\) or \(6k+1\).

Therefore, at least one of the numbers,\(p-1\) or \(p+1\), is divisible by \(6\).

Thus, \((p-1)(p+1)\) is always divisible by \(6\). \(_\square\)

## Proofs about Prime Numbers

## Let \(p\) be prime. If \(p|ab\), then \(p|a\) or \(p|b\).

Suppose \(p\) does not divide \(a\). Since the only divisors of \(p\) are \(1\) and \(p\) and \(p\) doesn't divide \(a\), we must have \(\gcd (a, p) =1\), so there exists some \(u\) and \(v\) such that \(ua+vp=1\). Then \(b=uab+vpb\); also \(p\) divides \(uab\) (since it divides \(ab\) by assumption) and \(p\) divides \(vpb\); so \(p\) divides their sum, which is \(b\). \( _\square \)