# 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, \ldots.\]

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\).
- As of January 2016, the largest prime number discovered 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 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 \)

## The Concept of EMIRP

An emirp (prime spelled backwards) is a prime number that results in a different prime when its decimal digits are reversed. This definition excludes the related palindromic primes. The term reversible prime may be used to mean the same as emirp, but may also, ambiguously, include the palindromic primes.

The sequence of emirps begins 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389, 701, 709, 733, 739, 743, 751, 761, 769, 907, 937, 941, 953, 967, 971, 983, 991, ... (sequence A006567 in the OEIS).

All non-palindromic permutable primes are emirps.

As of November 2009, the largest known emirp is 1010006+941992101×104999+1, found by Jens Kruse Andersen in October 2007.

The term 'emirpimes' (singular) is used also in places to treat semiprimes in a similar way. That is, an emirpimes is a semiprime that is also a (distinct) semiprime upon reversing its digits.