Number Theory and its Applications

3 Prime Numbers

“God may not play dice with the universe, but something strange is going on with the prime numbers.”

– Paul Erados,

3.1 Introduction

A prime number is an integer or a whole number that has only two factors 1 and itself. In other words, a prime number can be divided only by 1 and itself. Also primes are greater than 1. For example, 3 is prime as it fails to be divided evenly by any number except for 1 and 3. However, 6 is not because it can be evenly divided by 2 and 3.

The largest known prime number is 2^82,589,933 − 1, a number which has 24, 862, 048 digits when written in base 10. It was discovered by Patrick Laroche of the great internet Mersenne Prime search. Euclid recorded a proof that there does not exist any largest ...