Factorization or finding out factors

Breaking up a number into usable multiplicative components

factors-of12-apples

Factorization is one of the most basic operations in Maths

The process of finding out the factors or prime factors of a number is called factorization. This important process concept is used in many other problem situations, such as simplification, finding out HCF or finding out LCM and so on. It is one of the most basic operations in Maths.

To factorize a number, at each step we need to check whether the number is divisible by a suitable divisor prime number or not. Before taking up the method of factorization, we would go through efficient divisibility test methods.

Divisibility test methods

The following are the efficient divisibility test methods for a few prime divisors. If these few special rules are memorized and used, overall efficiency of calculation can be increased greatly without a significant memorization load.

Divisibility test for 2:

If the number is even, it is divisible by 2. For example, 24 is divisible by 2 as it is even (Test: even unit’s digit, that is, one of 0, 2, 4, 6, or 8).

Divisibility test for 3:

If the integer sum of the number is divisible by 3, the number itself is divisible by 3.

Integer sum of a number is the sum total of all its digits. For example, the number 123 is divisible by 3 as its integer sum = 1 + 2 + 3 = 6 is divisible by 3.

Reason:

  1. Any number can be expressed as a sum of the face values of its digits. Each face value is the product of the digit and its place value.
  2. Apart from unit's digit, all other place values are multiples of 10.
  3. When the number is divided by 3, effectively the sum of the face values is divided by 3, that is, each of the face values is divided by 3 and then summed up.
  4. In any such individual division, only the remainder contributes towards final divisibility. If the sum of these remainders is divisible by 3, the whole number would be divisible by 3.
  5. All multiples of 10 if divided by 3 generate a remainder of 1.
  6. Thus each face value except unit's digit contributes towards the sum of remainders with a value of $1\times{\text{digit}}= \text{digit}$.
  7. So, sum of remainders of division of face value of each digit by 3 = sum of the digits.
  8. Thus if 3 divides the sum of digits of an integer, it would divide the integer itself.

Let us understand the concept mathematically by testing the number 573 for divisibility by 3.

$\displaystyle\frac{573}{3} = \displaystyle\frac{5\times{10^2} + 7\times{10^1} + 3}{3}$

$=\displaystyle\frac{5\times{(99 +1)} + 7\times{(9 + 1)} + 3}{3}$

$= n + \displaystyle\frac{5 + 7 + 3}{3}$, where $n$ is the integer result of dividing the first part of the place values 99 and 9, with integer value of 186 in this case,

$=n + \displaystyle\frac{\text{Integer sum of 573}}{3}$

$=n + \displaystyle\frac{15}{3}$

$=n + 5 = 191$

As 15, or the integer sum of the number 573, is divisible by 3, the number itself will then be divisible by 3.

Divisibility test for 4:

If the number formed by the rightmost two digits of an integer is divisible by 4, the integer itself would be divisible by 4.

Reason:

  1. 1244 = 1200 + 44, where 44 represents the number formed by taking the rightmost two digits of the original number. As 1200, being a multiple of 100, is always divisible by 4, 1244 would be divisible by 4 if 44 is divisible by 4.
  2. By replacing the rightmost two digits of a number by 0s the number is transformed to a multiple of hundred and so is always divisible by 4. This number and its sum with the number formed by the taking the rightmost two digits form the original number itself. So if 4 divides the rightmost two digits, the integer automatically proves to be divisible by 4. 
  3. The technique used the basic tactic of breaking up the number suitably as a sum of two integers and checking the divisibility on its constituent parts. This is a general problem solving technique frequently used in mathematics and elsewhere.

Divisibility test for 5:

If the unit’s digit of the number is 0 or 5, the number would be divisible by 5. For example, 25 and 650 are divisible by 5. If you multiply any even number by 5, the 2 in the even number gets multiplied with 5 and generates a 10. The zero of 10 shows up as the unit’s digit of the number. Otherwise when the unit’s digit of the number is an odd digit, when multiplied with 5, it generates a 5 as the unit’s digit of the product.

Divisibility test for 6:

The number should be an even number divisible by 3. For example, 264 is even and so is divisible by 2. Also its integer sum is $2+6+4=12$ which is divisible by 3. So 264 has both 2 and 3 as its factors and is divisible by 6.

Divisibility test for 7:

If the difference between twice the unit's digit and rest of the number dropping the unit's digit is either 0 or divisible by 7, then the original integer is divisible by 7. We will take 4319 as an example,

$4319$ => $431 - 2\times{9}=413$.

We need to apply the same rule again on 413.

$413$ => $41 - 2\times{3}=35$

As 35 is divisible by 7, 413 is divisible by 7 and so 4319 is divisible by 7.

This rule is slightly complex and for large numbers have to be repeatedly applied. Furthermore, for small numbers (three digit numbers) its behaviour becomes uncertain.

Recommendation: Though this is a clever rule, for speed and accuracy of mental calculation in exam hall, it is better to directly divide the target integer by 7 for checking its 7 divisibility.

Divisibility test for 8:

If the last three digits of the integer is divisible by 8, the integer itself is divisible by 8.

Recommendation: This may be used only when the integer is very large. Otherwise it would be more efficient to divide the integer directly by 8.

Divisibility test for 9:

If the integer sum of the integer (sum of its digits) is divisible by 9, the integer itself would be divisible by 9. In this case when each of the face values of the integer is divided by 9 the remainder generated is 1, just as we had found when checking divisibility of 3.

Divisibility test for 10:

If the integer ends with 0 it is divisible by 10.

Divisibility test for 11:

If the difference between the sums of odd and even place digits of an integer (place starts as 1 on the rightmost place) is either 0 or is divisible by 11, the integer itself is divisible by 11.

As an example we would take the number, 45634578. The sum of odd place digits is,

$8+5+3+5=21$

and the sum of even place digits is,

$7+4+6+4=21 $

Both the sums are 21 and so their difference is 0. Thus the number 45634578 is divisible by 11.

Divisibility test for 12, 14, 15, 18:

Test for 12 will be a composite test for 3 and 4. Similarly for the other three numbers: tests for 2 and 7, 3 and 5, and 2 and 9 respectively.

Final recommendation:

The most efficient set of divisibility tests is recommended as,

  • If the number ends with 5 or 0, take the factor 5 or 10 out first.
  • If the number is even start test with 8, if fails then with 4, if fails then with 2.
  • If the number is odd start the test with 9, if fails test with 3.
  • Do the tests with 7 and 11 by direct division.
  • You need to repeat each test till all the same valued factors are taken out.

Finding the factors of an integer

To factorize a number, we find out the prime factors first. Once we get the prime factors, you can easily obtain other non-prime factors from the prime factors. To find the prime factors, the straightforward method is to check whether the number is divisible by the smallest prime number 2, then 3, then 5 and so on, repeating the process at each step.

Step 1: Check for the divisibility by 2, if so divide the number by 2. If the result is still divisible by 2 take 2 again as a second factor and divide the result by 2. Repeat the process till the result of division becomes odd. Example, $12\div{2}=6$, 2 is the first factor.

$6\div{2}=3$, another 2 is the second factor. The result of division is 3 which is a prime number and so it is the third factor of 12.

So, Factors of 12 are: 2, 2 and 3 or $12=2\times{2}\times{3}$.

Step 2: At this stage the output resulting number from the first step is odd, as we have taken out all the instances of factor 2 out of the number.

Now check the result of step 1 for divisibility by 3, and if divisible, divide it by 3. Continue this process till all factors of value 3 are taken out.

Step 3: Check the result of step 2 for divisibility by 5, and if divisible divide it by 5. Repeat this step till all the factors of value 5 are taken out.

Step 4: Check the result of step 3 for divisibility by 7, and if divisible divide it by 7. Repeat the step till all the factors of value 7 are taken out.

Step 5: Check the result of previous step for divisibility by the next prime number, if divisible divide it by the prime number being tested at this step. Repeat the step till all the factors of value of this prime number on test are taken out.

Notice that there is no termination point of this series of steps.

Termination of divisibility test

If at any step the number being tested for divisibility itself becomes a prime number, the process of factorization will stop and all the factors that could divide the original integer will be listed as the factors of the integer.

Special termination test: If at the start of any step, square of the prime number selected at this step for divisibility test is equal or more than the number being tested for divisibility, the process stops. The number will not have any more factors.

This in fact is the test for finding a prime number.

For a prime number, the divisibility test starts as usual with 2 and test is carried out for divisibility by the next prime number. But before the divisibility test, the square test is done for early termination. If all divisibility tests fail and the process terminates, then the original number is a prime number.

Example of the special square test for termination of divisibility

Let us assume we need to factorize the number 131.

As it is odd, we will first test for divisibility of 3 which fails.

The number doesn't end with 5 or 0, so it is not divisible by 5.

By dividing directly with 7 we find that 7 is not also a factor of 131.

The next prime number to test the divisibility is 11. Its square is stll less than 131, so we go on with the test. By direct division the test fails again.

The prime number on test now is 13 and its square 169 exceeds 131. So we can conclude, 131 is a prime number itself.

Use of Factorization

Factorization of numbers is one of the most important operations on numbers. It is used for many purposes. Three of the basic uses are:

  • Simplification of arithmetic expressions.
  • To find out Highest Common Factors of a set of numbers.
  • To find out the Least Common Multiple of a set of numbers.

We will deal with these later.


Let us now solve a few problems involving only the factorization concept and no higher level concept.

Example problems

Problem 1.

By what greatest prime number should 2176 be divided to leave remainder 9?

  1. 3
  2. 131
  3. 197
  4. 13

Solution:

The target number $= 2176 - 9 = 2167$.

First test by 3 fails. Second test by 7 also fails. The third test by 11 is successful as sum of alternate digits are equal, that is, 8. We divide 2167 then by 11 getting 197.

We have to test now 197 directly starting from 13 which fails. Square of the next prime divisor 17 is 289 and is much larger than 197. So 197 is a prime number and is the largest prime factor of 2167.

Answer: c: 197.

Problem 2.

The product of three consecutive natural numbers will always be divisible by,

  1. only 2
  2. 2 and 3
  3. only 3
  4. only 4

Solution:

Assuming $n$ as the first of the three consecutive natural numbers, the product would be,

$n\times{(n+1)}\times{(n + 2)}$.

If $n$ is an odd number, $n+1$ is even and so is divisible by 2, but $n+2$ will be another odd number. If $n$ is even to start with in any case the product will be divisible by 2. So we can say, whatever be the value of the first of the three consecutive natural numbers, the product of the three will always be divisible by 2.

Now let us assume that when the integer sum of the first number is divided by 3, the remainder is 2. Then the integer sum of the third number in the series will certainly be divisible by 3. In any other case then, the integer sum of the first or the second number will be divisible by 3.

So whatever be the nature of the first of the three consecutive natural numbers, their product will always be divisible by 2 and 3.

Answer: b: 2 and 3.

Problem 3.

What will be the missing digit in 78*2, if the four digit number is to be divisible by 11?

  1. 3
  2. 2
  3. 1
  4. 4

The sum of unit's and hundred's digit is 10 and if 78*2 is to be divisible by 11, the sum of 7 and the missing digit has to be 10 (it can't be 21). So, the missing digit must be 3.

Answer: a: 3.


Now we will leave you with a few exercise problems.

Exercise problems

Exercise problem 1.

Find the second largest prime number that will divide 5329 with 6 added to it.

  1. 5
  2. 11
  3. 93
  4. 97

Exercise problem 2.

Find the missing digit in 4*379, if the five digit number is to be divisible by 9.

  1. 1
  2. 3
  3. 4
  4. 7

Exercise problem 3.

By which largest prime number should 5894 be divided to leave 5 as remainder?

  1. 13
  2. 151
  3. 153
  4. 17

The concept of factorization when used in the higher level concept topics of Highest Common Factor (or HCF) and Lowest Common Multiple (or LCM), a large variety of problems are created. In itself factorization concept is primarily a helper concept or base concept as it is used extensively in richer concept topics of HCF, LCM, Simplification and so on.

But always remember,

Ability to find out factors quickly is crucial in solving a large variety of problems successfully within time.

Recommendation: As practice, you should do a large number of pure and simple factorization as a drill to speed up your ability to factorize a number quickly and correctly.

Factorization is a basic mental math ability.

You may refer to our detailed previous article on numbers and number system as it is the foundation of maths as whole, and our next article on HCF and LCM where the concepts on Facorization are heavily used.


Answers to exercise problems

Exercise problem 1. Answer b: 11.

Exercise problem 2. Answer c: 4.

Exercise problem 3. Answer b 151.