Primes/Introduction

Introduction

There are multiple ways to define a prime number. We can define a prime number as "A natural number who has exactly two factors." It goes without saying that the two factors are different numbers.

For a prime number $p$, the two factors are: the number "1" and $p$ itself. "1" is a factor of each number, and each number is a factor of itself. This means, a natural number $a$ is a prime number if and only if there does exists any number $b$ such that $a/b$ is not an integer for every integer $b$ from $1$ to $a$, not including $1$ and $a$. It can be also denoted as $a\equiv k\ (mod\ b)$ where $k\neq 0$.

The first natural number is 1. As per the definition, there should exist only two factors, and both of them should be distinct. Here $p=1$. So, the factors are 1 and 1. Since there is only one factor, "1" does not satisfy the condition of a prime number. It also fails to satisfy the condition of composite number, and hence, "1" is neither prime nor composite. A natural number is said to be composite if it has at least three distinct factors. So, the set of natural numbers ℕ is the collection of all prime numbers, all composite numbers and "1". ℕ = {{n: n ∈ prime numbers} ∪ {m: m ∈ composite numbers} ∪ 1}.

The first five prime numbers are: $2,3,5,7,and\ 11$.

$2$ is the first prime number and it is also the only even number which is prime. Any positive even number $E$ can be represented in the form of $2m$ where $m$ is a natural number. Thus, for $m>1$; $1,2,\ m,\ and\ 2m$ are the factors of the even number $E$. So, except $2$, there can be no other even prime number.

Though the frequency of occurrence of primes decreases as we move towards infinity, infinitely many primes exists. Euclid proved that there are indeed infinitely many prime numbers.

To prove there are infinite prime numbers by the method of contradiction, let us assume, there are finite numbers of primes and their set is represented by $P$. Consider two numbers $m,n$, where m = (p × p₁ × p₂ × p₃ × ... p_n) + 1. And $n=m+1$. It goes without saying that any number in the set $P<m,n$.

As per our assumption, there are no more primes left. And as per the fundamental theorem of mathematics, $n$ is a product of at least two primes if $n$ is not a prime. Thus there should be a prime number $p$ which belongs to $P$ which divided $n$. $m$ when divided by $p$ leaves no remainder. Thus, it will leave leave the remainder 1 in the case of $n$, and no prime can completely divide 1. For the fundamental theorem of mathematics to hold true, there should be at least one more prime which is not present in the set $P$, and our assumption is false. And thus, there are infinitely many primes.

Intuitively, it can be said as:

{$P\ :\ P\ is\ the\ group\ of\ all\ primes$}.
m = (p × p₁ × p₂ × p₃ × ... p_n) + 1,\ $n=m+1$. $m\equiv 0\ (mod\ p)$
$m+1=n\equiv 1\ (mod\ p)$

A composite number has at least one factor other than 1 and itself. So, to check, if the given number $x$is prime, check for all integers between 2 and ${\sqrt {x}}$ both inclusive. If none if them divides $x$ completely, then it is safe to conclude that the number is a prime number.

A function in C programming language for checking if the given number is prime or not, the code is:

int prime (int x) {
	int i = 2;
  	if(x < 2)
		return FALSE;
	for(i; i * i <= x; i++) {
		if(x % i == 0)
			return FALSE;
	}
	return TRUE;
}

This function would return 1 or TRUE if the number $x$ is prime else return 0 or FALSE.