Divisors, prime numbers, and prime factorisations

Calculating with numbers: Computing with integers

Divisors, prime numbers, and prime factorisations

When the remainder of a division with remainder is zero, then we say that the division terminates. For example, \(156:13=12\). The we have \(156=12\times 13\). Also, the division \(156:13\) terminates and has the outcome \(12\). The numbers \(12\) and \(13\) are divisors of \(156\) and the relation \(156=12\times 13\) is called a decomposition into factors.

From these two divisors, \(12\) can be decomposed into factors, namely \(12=3\times 4\). So \(156=3\times 4\times 13\). We can go one step further and factorise \(4\) as \(4=2\times 2=2^2\). You cannot decompose the number \(256\) into more factors because each number \(2\), \(3\) and \(13\) is only divisible by \(1\) and the number itself. The numbers \(2\), \(3\) and \(13\) are called prime numbers , primes in short, and factorisation \(156=2^2\times 3\times 13\) is called a prime factorisation of \(156\). You see in this example that it is also good practice to collect primes that occur more than once and write them as power. We call \(2\), \(3\) and \(13\) the prime factors of the number \(156\).

Prime number

A prime number, or a prime, is a natural number with exactly two divisors.

All prime numbers less than thirty are: \(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\), \(23\) and \(29\).
\(\phantom{x}\)

Each prime number can only be divided by \(1\) and the number itself. But this is not a defining feature, because then \(1\) would be a prime number. But that is not true.

Infinitely many primes There exist infinitely many primes. You can construct a new prime number from any finite set of primes. The following example illustrates how.

Suppose you have the primes \(2\), \(3\), \(5\), \(13\) and \(17\). Because division with remainder of \[1+2\times 3\times5\times 13\times 17=6631\] by each of these prime numbers yields the remainder \(1\), none of these prime numbers is a divisor of \(6631\). Among the divisors of \(6631\) there must still be a prime divisor other than \(2\), \(3\), \(5\), \(13\), and \(17\). Because \(6631=19\times 349\) and both \(19\) and \(349\) are prime, we have found two new prime numbers.

The following theorem illustrates that you can consider primes as the building blocks of the natural numbers.

Prime factorisation

Every natural number greater than \(1\) can be written as a product of a finite number of primes.
This so-called prime factorization is unique, up to the ordering of the factors.

Examples \[\begin{aligned}30&=2\times 3\times 5\\ \\ 40&=2\times 2\times 2\times 5\\&=2^3\times 5\end{aligned}\]

Recognizing small prime factors 2, 3 and 5 A number is divisible by

\(2\) when the last digit of the number is divisible by \(2\);
\(3\) when the sum of the digits of the number is divisible by \(3\);
\(5\) when the last digit of the number is \(0\) or \(5\).

There exist mathematical algorithms that can compute the prime factorisation of a natural number. But generally, the finding of prime factors of a number and the building up of a prime factorisation of a number via pencil-and-paper is hard work. You do this by systematically trying out larger prime divisors. Whenever you find a prime divisor, divide by it, and proceed with the quotient. You are ready when you end up with a quotient that is prime.

Decompose \(99\) into prime factors.

\(99=3\times 3\times 11=3^2\times 11\)

Try first to divide by the smallest prime divisor, namely \(2\).
Omdat \(99\) niet deelbaar is door \(2\), luidt het advies om het volgende priemgetal \(3\) te proberen.
Dat levert hier succes op want \(99=3\times 33\). Ga nu verder met het ontbinden van \(33\).
De eerstvolgende priemdeler is \(3\) want \(33=3\times 11\).
Verder is \(11\) een priemgetal.

The process ends here with a prime and so we are ready with the prime factorisation of \(99\): \[99=3\times 3\times 11=3^2\times 11\]
In summery, the calculation process is as follows: \[\begin{aligned} 99&=\blue{3}\times 33\\ 33&=\blue{3}\times \blue{11}\end{aligned}\] The blue numbers \(3\), \(3\), and \(11\) are the three prime factors of \(99\).

New example