How do you find factors of a composite number?

Answer 1

There are a few ways to go about factoring. You can decide what works best for you. I always find the prime factorization first. Let's look at a random number: 108

The prime factorization can be found by using a factor tree.

108

54,2

27,2,2

9,3,2,2

3,3,3,2,2

2^2 x 3^3 = 108

Half of the factors will be less than the square root, half greater. If the number is a perfect square, there will be an equal number of factors on either side of the square root. In this case, the square root is between 10 and 11.

Adding one to the exponents of the prime factorization and multiplying them will tell you how many factors there are. In this case, the exponents are 2 and 3. Add one to each. 3 x 4 = 12

108 has 12 factors. Six of them are 10 or less, six of them are 11 or greater. All we have to do is divide the numbers one through ten into 108. If the result (quotient) turns out to be an integer, you've found a factor pair. Knowing the rules of divisibility will make that even easier.

108 is divisible by...

1 because everything is.

2 because it's even.

3 because its digits add up to a multiple of 3.

4 because its last two digits are a multiple of 4.

6 because it's a multiple of 2 and 3.

9 because its digits add up to a multiple of 9.

That's six factors less than 10. Divide them into 108. That's the rest of them.

(108,1)(54,2)(36,3)(27,4)(18,6)(12,9)

1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108

Notice that all of those numbers, except for 1, can also be found in the prime factorization.

Answer 2

There is no simple answer.

For small composite numbers you can try factorising by 2, then by 3, and then 5 and so on trying primes up to the square root of the number. If successful, each factor will reduce the size of the number that needs to be factorised and make the task somewhat simpler.

However, if the composite number is a multiple of two very large primes (each prime hundreds of digits long), you don't stand much of a chance. This very property is central to digital encryption.