Saturday, September 10, 2011

Alternative definition for the prime numbers

I was watching this video recently and mentioned the presenter pointing to the definition for the prime numbers we all know from the school, i.e.

Classical Definition: A natural number p > 1 is prime if 1 and p are its only divisors.

However, there is an alternative way to define the prime numbers (the one I learned when I was doing my university degree).

Alternative Definition: A natural number p > 1 is prime if for ∀ a, b - integers satisfying p | a⋅bp | a or p | b

(Note: "p | a" means "p divides a" or "a is divisible by p").

Sounds complicated? Not really. For example, according to this definition 4 isn't a prime because it divides 2⋅2, but doesn't divide 2.

With this definition, the classical one is, in fact, a theorem:

Theorem: A natural number p > 1 is prime ⇔ 1 and p are its only divisors.

Let's prove it ...

Step 1. Let's assume that p is prime and show that 1 and p are its only divisors.

We will start by supposing the contrary, i.e. there ∃ s,tN, both ∉ {1,p}, so that p=s⋅t. This means p | s⋅t and because p is prime ⇒ p | s or p | t. Let's assume p | ss=q⋅p, q - positive integer ⇒ p=s⋅t=q⋅p⋅t ⇒ 1=q⋅t which has sense when t=1 and q=1 ⇒ s=p - contradiction. So 1 and p are the only divisors for p - prime.

Step 2. Let's assume that the only divisors of p are {1, p} and show that p is prime.

Again we will suppose the contrary, i.e. p isn't prime. This means there ∃ a,b - integers so that p | a⋅b and p doesn't divide a and p doesn't divide b. We can write a⋅b=p⋅q, q - positive integer. We should note that (a,p) = 1 (greatest common divisor), otherwise if (a,p)=d>1 ⇒ d | p which means d = p and p | a - contradiction, so (a,p) = 1. From Bezout Theorem this means that there ∃ k,z - integers so that k⋅p+z⋅a=1 ⇔ k⋅p⋅b+z⋅a⋅b=bk⋅p⋅b+z⋅p⋅q=bp⋅(k⋅b+z⋅q)=b or p | b - contradiction. So p is prime.

It is important to note that if we consider the classical definition for the prime numbers, then the alternative definition becomes what is known as Euclid Lemma.

In other words, it doesn't really matter which definition we adopt (for integer numbers, for more details see this link), because one is provable from another.