Prime numbers

Factorization 30 6 × 5 2 × 3 × 5 45 9 × 5 3 × 3 × 5 30 45 = 2 × 3 × 5 3 × 3 × 5 = 2 3

Fig.1. Factorization of 30 and 45. Numbers 2, 3 and 5 are prime numbers. Numbers 30 and 45 share prime factors 3 and 5.

Fundamental theorem of arithmetic

With multiplication, the factors (e.g. 2 × 3) are given and the product (6) needs to be calculated. But we can also work in opposite direction: a number is given, and factors of that number need to be calculated. This breaking down into factors is called factorization or factoring. In arithmetic, factorization specifically refers to finding integer factors. In case of integer factorization the given number is divisible by all calculated factors.

Also division can be viewed as the opposite of multiplication, only then we are not necessarily calculating integer factors. In 14 ÷ 4 = 3r2 both 4 and 3 are not factors of 14.

Multiply:

2 × 3 = 6

3 × 4 = 12

Factorize:

6 = 2 × 3

12 = 3 × 4

12 = 2 × 6

So, 12 can be factorized in two ways. But 4 and 6 can again be factorized. In the example above, 12 is not fully factorized.

12 = 3 × 4 = 3 × 2 × 2.

12 = 6 × 2 = 3 × 2 × 2.

Note that we are operating within the domain of positive integers, greater than 1. Including factor 1 would be rather pointless, since any number can be factorized into an arbitrary number of factors 1, for instance, 6 = 1 × 1 × 1 × 2 × 3.

Fully factorizing 12 will always result in 2 × 2 × 3 (regardless the order of factors of course). This is an important property of natural numbers greater than 1. In the above examples 2 and 3 cannot be factorized any further. Such numbers are called prime numbers. In 12 = 2 × 2 × 3 the number 12 is factorized into its prime factors.

In general, "factorizing" means converting something that is not a product (not a multiplication) to a product of any kind of factors. Factorization in arithmetic generally refers to factorizing a positive integer greater than 1 into its prime factors.

Definitions

"x is divisible by y" or "y (evenly) divides x" if and only if both y and the quotient are positive integers and there is no remainder.

A definition of a prime number:

A number is a prime number if and only if that number is an integer greater than 1 and cannot be factorized into other integers greater than 1.

An alternative definition:

A number is a prime number if and only if that number is an integer greater than 1 and only divisible by 1 and by the number itself.

An important property of natural numbers:

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or composite, that is, a unique product of primes.

Prime and composite numbers

All composite numbers have their own unique product of prime factors. Such a product of prime factors can have multiple equal factors. In that case these factors are often written as a power:

12 = 2 × 2 × 3 = 22 × 3.

8 = 2 × 2 × 2 = 23.

81 = 3 × 3 × 3 × 3 = 34.

The list of prime numbers starts of as: 2, 3, 5, 7, 11, etc. By convention, 1 is excluded from the set of prime numbers, for reasons mentioned earlier.

Next table shows all prime numbers and composite numbers with their prime factors, up to 100:

11 21 = 3 × 7 31 41 51 = 3 × 17 61 71 81 = 34 91 = 7 × 13
2 12 = 22 × 3 22 = 2 × 11 32 = 25 42 = 2 × 3 × 7 52 = 22 × 13 62 = 2 × 31 72 = 23 × 32 82 = 2 × 41 92 = 22 × 23
3 13 23 33 = 3 × 11 43 53 63 = 32 × 7 73 83 93 = 3 × 31
4 = 22 14 = 2 × 7 24 = 23 × 3 34 = 2 × 17 44 = 22 × 1154 = 2 × 33 64 = 26 74 = 2 × 37 84 = 22 × 3 × 7 94 = 2 × 47
5 15 = 3 × 5 25 = 52 35 = 5 × 7 45 = 32 × 5 55 = 5 × 11 65 = 5 × 13 75 = 3 × 52 85 = 5 × 17 95 = 5 × 19
6 = 2 × 3 16 = 24 26 = 2 × 13 36 = 22 × 32 46 = 2 × 23 56 = 23 × 7 66 = 2 × 3 × 11 76 = 22 × 19 86 = 2 × 43 96 = 25 × 3
7 17 27 = 33 37 47 57 = 3 × 19 67 77 = 7 × 11 87 = 3 × 29 97
8 = 23 18 = 2 × 32 28 = 22 × 7 38 = 2 × 19 48 = 24 × 3 58 = 2 × 29 68 = 22 × 1778 = 2 × 3 × 13 88 = 23 × 11 98 = 2 × 72
9 = 32 19 29 39 = 3 × 13 49 = 72 59 69 = 3 × 23 79 89 99 = 32 × 11
10 = 2 × 5 20 = 22 × 5 30 = 2 × 3 × 5 40 = 23 × 5 50 = 2 × 52 60 = 22 × 3 × 5 70 = 2 × 5 × 7 80 = 24 × 5 90 = 2 × 32 × 5 100 = 22 × 52

Can you explain why 17 or 23 or 47 or 73 are not in the multiplication table? And why is 27 in the multiplication table, but not 26? And can you explain why 2 seems to be the only even prime number?

Of course we can continue the list after 100. In fact, no matter how far you go on the number line, you will always keep finding prime numbers between the composite numbers. There is no greatest prime number defined. The set of prime numbers is infinite, as is the set of positive integers. Appendix A shows a proof that the set of primes is infinite.

Algorithms

But how do you know if a number is prime or composite, and if composite, how do you find its prime factors? In this section we will discuss two simple algorithms: One to find primes and one to prime factorize a composite number.

Factorize an integer < 100 000.

Sieve of Eratosthenes

Among other algorithms, the sieve of Eratosthenes is a simple and famous algorithm for finding all prime numbers up to any given number. This algorithm is named after the man who introduced it, Eratosthenes of Cyrene, a Greek scholar who lived more than 2000 years ago. Suppose we need to find all the prime numbers less than or equal to 20. The sieve of Eratosthenes distinguishes the following steps:

  1. 1. First create a list of consecutive integers from 2 through n = 20:
    234567891011121314151617181920
  2. 2. Let p initially equal 2 (the smallest prime number) and cancel out all multiples of p (except p itself) in the list, that is, 2 × p, 3 × p, 4 × p, 5 × p, etc.
    234567891011121314151617181920
  3. 3. Find the smallest number in the list, greater than p and smaller than n, that is not canceled out. If there is no such number, then stop and the numbers remaining not marked in the list are all the primes, otherwise, if there is such number, let p now equal this number and repeat from step 2.
    234567891011121314151617181920

    In our example, in the third step, all multiples of 3 were canceled in the list above (3 × 3 = 9, 4 × 3 = 12 and 5 × 3 = 15). Are there any multiples of 4, 5, etc. left to cancel out?

Note that many numbers will be canceled out more than once. Also note that all numbers picked for p are prime numbers themselves. After all, multiples of a composite number must already have been canceled out in an earlier iteration. For instance, multiples of 6 have already been canceled out when p was 2 and again when p was 3. Thus in short it comes down to sifting out the multiples of all primes smaller than n.

As a refinement, it is sufficient to cancel out numbers in each step 2 starting from p × p. All the smaller multiples of p have already been canceled out in earlier iterations. In the example above, after p = 3 the next p would be 5. But 5 × 5 = 25 is already greater than n = 20, thus the algorithm can be stopped. After canceling all multiples of 2 and 3, all the numbers left are the prime numbers less than or equal to 20.

If we want to know if a single given number is prime or composite, we can follow the same algorithm and stop if the number cancels out or if all primes smaller than the number have been tried. Number 20 is not prime, because it is a multiple of 2. Number 19 is prime, because it is not a multiple of any prime smaller than 19.

So: To check whether a number is prime or composite: Find out whether this number is a multiple of any prime number whose square is less than or equal to this number. If it is, the number is composite; if not, the number is prime.

Is 101 prime?

101 ÷ 2 has a remainder,
101 ÷ 3 has a remainder,
101 ÷ 5 has a remainder,
101 ÷ 7 has a remainder,
11 × 11 = 121, which is greater than 101. We can stop.

Conclusion: 101 is prime.

Is 343 prime?

343 ÷ 2 has a remainder,
343 ÷ 3 has a remainder,
343 ÷ 5 has a remainder,
343 ÷ 7 = 49, 343 is a multiple of 7 (343 = 7 × 49 = 73).

Conclusion: 343 is composite.

Trial division

There are also several algorithms available for prime factorizing a composite number. Trial division is a slow and laborious algorithm, but it is the most straightforward:

  1. 1. Let n be the positive integer to be factorized and let p be the smallest prime number 2.
  2. 2. While n > 1
    1. If n is divisible by p, then add p to the list of prime factors and let n be equal to the quotient,
      else, add 1 to p.

In JavaScript:


function factorize(n){
  let p = 2;
  let primesList = [];
  while (n > 1) {
    if (n % p === 0) {  // If remainder of n/p is zero, n is divisible by p
      primesList.push(p); // Add p to the primes list
      n = n / p; // let n be equal to the quotient
    } else {
      p = p + 1; // add 1 to p
    }
  }
  return primesList;
}

factorize(21); // returns: [ 3, 7 ]

Prime factorize n = 21:

m ÷ p
21 ÷ 2
21 ÷ 3 = 7
7 ÷ 3
7 ÷ 4
7 ÷ 5
7 ÷ 6
7 ÷ 7 = 1

Conclusion: 21 = 3 × 7.

Note that if this algorithm had known that 7 was a prime, the number of steps could have been reduced to just 2. But this algorithm is not aware of prime numbers, and there is no easy or fast test for the primality of a number.

Prime factorize n = 46:

m ÷ p
46 ÷ 2 = 23
23 ÷ 2
23 ÷ 3
23 ÷ 4
23 ÷ 21
23 ÷ 22
23 ÷ 23 = 1

Conclusion: 46 = 2 × 23.

Not all steps are needed in the example above. As we have seen, if p × p is greater than m, we know that m is prime. So we could have stopped trying after 23 ÷ 4 since in the next step 5 × 5 is greater than 23. The more efficient variation of the trial division algorithm will then be as follows:

  1. 1. Let n be the positive integer to be factorized and let p be the smallest prime number 2.
  2. 2. While p2n
    1. If n is divisible by p, then add p to the list of prime factors and let n be equal to the quotient,
      else, add 1 to p.
  3. 3. Add n to the list of prime factors, unless n = 1 (in case the given number to factorize was 1).

In JavaScript:


function factorize(n){
  let p = 2;
  let primesList = [];
  while (p * p <= n) { // while p × p ⩽ n
    if (n % p === 0) {  // If remainder of n/p is zero, n is divisible by p
      primesList.push(p); // Add p to the primes list
      n = n / p; // let n be equal to the quotient
    } else {
      p = p + 1; // add 1 to p
    }
  }
  if (n != 1) primesList.push(n); // if n is not 1, add n to primes list
  return primesList;
}

factorize(46); // returns: [ 2, 23 ]

Prime factorize n = 46:

46 ÷ 2 = 23
23 ÷ 2
23 ÷ 3
23 ÷ 4

Conclusion: 46 = 2 × 23.

An other improvement is to only test for odd factors (except 2), since the only even prime number is 2.

  1. 1. Let n be the positive integer to be factorized and let p be the smallest prime number 2.
  2. 2. While n is divisible by 2
    1. add p to the list of prime factors and let n be equal to the quotient.
  3. 3. Let p = 3.
  4. 4. While p2n
    1. If n is divisible by p, then add p to the list of prime factors and let n be equal to the quotient,
      else, add 2 to p.
  5. 5. Add n to the list of prime factors, unless n = 1 (in case the given number to factorize was 1).

In JavaScript:


function factorize(n){
  let p = 2;
  let primesList = [];
  while (n % 2 === 0) { // while n is divisible by 2
    primesList.push(p); // Add p to the primes list
    n = n / p; // let n be equal to the quotient	
  }
  p = 3;
  while (p * p <= n) { // while p × p ⩽ n
    if (n % p === 0) {  // If remainder of n/p is zero, n is divisible by p
      primesList.push(p); // Add p to the primes list
      n = n / p; // let n be equal to the quotient
    } else {
      p = p + 2; // add 2 to p; try only odd factors
    }
  }
  if (n != 1) primesList.push(n); // if n is not 1, add n to primes list
  return primesList;
}

factorize(416); // returns: [ 2, 2, 2, 2, 2, 13 ]

Some examples:

Prime factorize n = 21:

m ÷ p
21 ÷ 2
21 ÷ 3 = 7
7

Conclusion: 21 = 3 × 7.

Prime factorize n = 20:

m ÷ p
20 ÷ 2 = 10
10 ÷ 2 = 5
5 ÷ 2

Conclusion: 20 = 2 × 2 × 5.

Prime factorize n = 260:

260 ÷ 2 = 130
130 ÷ 2 = 65
65 ÷ 2
65 ÷ 3
65 ÷ 5 = 13
13

Conclusion: 260 = 2 × 2 × 5 × 13.

Prime factorize n = 416:

416 ÷ 2 = 208
208 ÷ 2 = 104
104 ÷ 2 = 52
52 ÷ 2 = 26
26 ÷ 2 = 13
13 ÷ 2
13 ÷ 3

Conclusion: 416 = 25 × 13.

How will this algorithm progress if the number to be factorized is prime?

Executing the sieve of Eratosthenes algorithm or the trial division algorithm with only pen and paper can be quite laborious. Later in this book it will show that prime numbers are often used in arithmetic. Through practicing arithmetic you will learn to know most primes under 100.

Divisibility rules

There are some "tricks" to find out if a number is divisible by an other number. They are called the divisibility rules. With the divisibility rules you can quickly see if a number is divisible by 2, 3, 5, 7, 11 or 13. They can be useful when applying the algorithms discussed above.

A number is divisible by 2 if and only if the last digit, the ones digit, is 0, 2, 4, 6, or 8. Numbers divisible by 2 are called even, numbers not divisible by 2 are called odd.

A number is divisible by 3 if and only if the addition of all digits is divisible by 3.

321: 3 + 2 + 1 = 6.
6 is divisible by 3 and thus also 321 is divisible by 3.

86765574: 8 + 6 + 7 + 6 + 5 + 5 + 7 + 4 = 48 and 4 + 8 = 12.
12 is divisible by 3 and thus also 48 and thus also 86765574 are divisible by 3.

A number is divisible by 5 if and only if the last digit, the ones digit, is 0 or 5.

A number is divisible by 7 if and only if the subtraction of 2 times the last digit from the number formed by the rest of the digits is divisible by 7.

91: 9 − (2 × 1) = 7.
7 is divisible by 7, thus 91 is also divisible by 7.

119: 11 − (2 × 9) = −7.
−7 is divisible by 7, thus 119 is also divisible by 7.

343: 34 − (2 × 3) = 28.
28 is divisible by 7, thus 343 is also divisible by 7.

7644: 764 − (2 × 4) = 756 and 75 − (2 × 6) = 63.
63 is divisible by 7, thus 756 and thus 7644 are also divisible by 7.

A number is divisible by 11 if and only if the subtraction of the last digit from the number formed by the rest of the digits is divisible by 11.
Or: If and only if the alternating subtraction and addition of all digits is divisible by 11.

88: 8 − 8 = 0.
0 is divisible by 11, thus 88 is also divisible by 11.

111: 11 − 1 = 10.
10 is not divisible by 11, thus 111 is not divisible by 11.

1111: 111 − 1 = 110 and 11 − 0 = 11.
110 is divisible by 11, thus 1111 is also divisible by 11 (11 × 101).

1111: 1 − 1 + 1 − 1 = 0.
0 is divisible by 11, thus 1111 is also divisible by 11.

72479: 7 − 2 + 4 − 7 + 9 = 11.
11 is divisible by 11, thus 72479 is also divisible by 11.

A number is divisible by 13 if and only if the subtraction of 9 times the last digit from the number formed by the rest of the digits is divisible by 13.

4199: 419 − (9 × 9) = 338 and 33 − (9 × 8) = −39.
−39 is divisible by 13, thus 338 and thus 4199 are also divisible by 13.

There are rules for the divisibility by 17, by 19, by 23 etc. but they do not necessarily always make things easier. You can of course also always perform a long division to see if a number is divisible by some other number. Also for the divisibility by composite numbers there are rules: Divisible by 4 if the last two digits form a number that is divisible by 4, divisible by 8 if the last three digits form a number that is divisible by 8, divisible by 6 if the number is divisible by 2 and by 3 and divisible by 9 if the addition of all digits is divisible by 9 (the same procedure as with the divisibility by 3). Can you formulate divisibility rules for 10 and 12?

Appendix A provides proofs for the divisibility rules.