Today we will learn about prime numbers - a basic building block of arithmetic.
A prime number is a natural number greater than 1 and has no divisors other than 1 and itself. For example, the numbers 2, 3, 5, 7, 11, 13 are prime numbers. The number 9 is not a prime number because it is divisible by 3. The number 2012 is not a prime number because it is divisible by 2.
Any natural number greater than 1 can be written as a product of prime numbers. Below are some examples $$4 = 2 \times 2 = 2^2, \quad 6 = 2 \times 3, \quad 8 = 2 \times 2 \times 2 = 2^3,$$ $$9 = 3 \times 3 = 3^2, \quad 10 = 2 \times 5, \quad 12 = 2 \times 2 \times 3 = 2^2 \times 3,$$ $$2012 = 2 \times 2 \times 503 = 2^2 \times 503,$$ $$2013 = 3 \times 11 \times 61.$$ So from prime numbers, we can build up the whole natural numbers. Prime numbers can be thought of as building blocks to build up other numbers.
We know that each individual of us has a unique appearance and characteristics because each person has a distinct set of genes. Each prime number can be considered as a gene, and from these "prime number genes", other numbers can be formed.
For example,
- The number 4 has two genes 2 because $4 = 2^2$,
- The number 6 has one gene 2 and one gene 3 because $6=2 \times3$,
- The number 12 has two genes 2 and one gene 3 because $12=2^2 \times 3$.
Multiplication of two numbers corresponding to addition of their two gene collections.
Let us look at the multiplication. We have $12 = 2^2 \times 3$ and $10 = 2 \times 5$. Product of $12$ and $10$ is $120 = 2^3 \times 3 \times 5$. The number 12 has two genes 2 and one gene 3. The number 10 has one gene 2 and one gene 5. Product of 12 and 10, the number 120, has a gene collection of three genes 2, one gene 3 and one gene 5. This gene collection is equal to the combination of the two gene collections of 12 and 10.
Divisibility between two numbers corresponding to comparing the two gene collections.
We say that a number $a$ is divisible by a number $b$ if there is a number $c$ so that $a = bc$. In this case, $a$ is called a multiple of $b$ and $b$ is called a divisor of $a$.
If $a$ and $b$ are factored as $$a = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$$ $$b = p_1^{\beta_1} p_2^{\beta_2} \dots p_k^{\beta_k}$$ then $a$ is divisible by $b$ if and only if $\alpha_1 \geq \beta_1$, $\alpha_2 \geq \beta_2$,..., $\alpha_k \geq \beta_k$. So $a$ is divisible by $b$ iff the gene collection of $a$ is greater than or equal to the gene collection of $b$.
 |
| 6 is a divisor of 240 because the gene collection of 6 is fewer than the gene collection of 240 |
For example, the number 6 has one gene 2 and one gene 3, whereas the number 240 has four genes 2, one gene 3 and one gene 5. So 240 is divisible by 6, 240 is a multiple of 6 and 6 is a divisor of 240.
 |
| the two gene collections of 6 and 10 cannot be compared |
On the other hand, among 6 and 10, no number is a divisor of the other because their gene collections cannot be compared. Comparing on gene 2, the number 6 and the number 10 have the same amount. However, the number 6 has more gene 3 than the number 10, and if we do comparison on gene 5 then the number 10 has more.
The greatest common divisor - The least common multiple.
Since $252 = 2^2 \times 3^2 \times 7$ and $120 = 2^3 \times 3 \times 5$, the greatest common divisor of 252 and 120 is $2^2 \times 3 = 12$ and the least common multiple of 252 and 120 is $2^3 \times 3^2 \times 5 \times 7=2520$.
In the above figure, it is easy to see that $$gcd(a,b) ~lcm(a,b) = ab$$
Therefore, the greatest common divisor can be calculated from the least common multiple and vise versa.
$$gcd(a,b) = \frac{ab}{lcm(a,b)}, \quad lcm(a,b) = \frac{ab}{gcd(a,b)}$$
With $$a = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$$ $$b = p_1^{\beta_1} p_2^{\beta_2} \dots p_k^{\beta_k}$$ then $$gcd(a,b) = p_1^{\min{(\alpha_1, \beta_1)}} p_2^{\min{(\alpha_2, \beta_2)}} \dots p_k^{\min{(\alpha_k, \beta_k)}},$$ $$lcm(a,b) = p_1^{\max{(\alpha_1, \beta_1)}} p_2^{\max{(\alpha_2, \beta_2)}} \dots p_k^{\max{(\alpha_k, \beta_k)}}.$$
Since $\min{(\alpha_i, \beta_i)} + \max{(\alpha_i, \beta_i)} = \alpha_i + \beta_i$, we can derive a proof of the equality $$gcd(a,b) ~lcm(a,b) = ab.$$
Coprime means no common gene.
Two numbers $a$ and $b$ are called coprime if their greatest common divisor is equal to 1. It follows that their two gene collections have no common genes. The least common multiple of two coprime numbers $a$ and $b$ is equal to their product $ab$.
In the below example, 6 and 35 are coprime because they do not have any common gene.
The number 1 corresponding to the empty gene collection.
If $$a = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$$ then $$a \times 1 = a = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$$ So $$1 = p_1^0 p_2^0 \dots p_k^0$$ It means that the number 1 has an empty gene collection.
If $$a = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$$ then $$a \times 1 = a = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$$ So $$1 = p_1^0 p_2^0 \dots p_k^0$$ It means that the number 1 has an empty gene collection.
What is the gene collection of the number 0?
Let us stop here with a tricky question, "what is the gene collection of the number 0?" If you know the answer, please write a comment here and share with us.
See you again in the next post.
Homework.
1. Prove that $gcd(a,b) = gcd(a, b-a)$.
2. Prove that if $ab$ is divisible by $c$ and $b$ is coprime to $c$ then $a$ is divisible by $c$.
3. Prove that there are an infinite number of prime numbers.