Any technique to manually find the prime decomposition of a number less than 3000?

Question

I've seen a question in a math exam, asking to find the prime decomposition of 2014. It's 2*19*53.

I found it odd and a little fastidious at first to try to find the multiples of 1007, trying to divide 1007 by 3, then 7, then 11, then 13, then 17, then 19.

Any way to quickly eliminate possible multiples ?

I've got a weird technique to check if a number that doesn't immediately look like a non-prime really is a prime or not.

For example, 143 is ambiguous. if I substract 13 to it, I have 130+13, which immediately shows it's a multiple of 13.

But for 221, which is 13*17, my technique becomes useless.

I've also seen the technique where you add up each digit, but I don't understand why this method works.

Don't you know any technique to either quickly find multiples, or know if the number is a prime ? Or should I just start remembering them individually ? Would it work for number less than 3000 ? Those numbers are not so big...

Answer 1

Here are two tricks that, especially used in combination, can check if the positive integer $n$ is divisible by the positive integer $d$.

(1) $n$ is divisible by $d$ if and only if $n+kd$ is divisible by $d$ (this holds for any integer $k$. Thus you can add or subtract multiples of $d$ from $n$ without affecting divisibility by $d$.

(2) If $n=bc$ and $c$ is relatively prime to $d$, then $n$ is divisible by $d$ if and only if $b$ is divisible by $d$. (That is you can cancel a factor from $n$ provided that factor is relatively prime to $d$.)

Let's see how this can be applied to your problem of factoring $2014$.

First we take out the obvious factor of $2$, leaving us with $1007$ to factor.

Since the sum of digits is not divisible by $3$, $1007$ is not divisible by $3$.

Also $1007$ is obviously not divisible by $5$.

Next, using (1), $1007$ is divisible by $7$ iff $1007-7=1000$ is divisible by $7$, which it is not.

Next, $1007$ is divisible by $11$ iff $1007+33=1040$ is divisible by $11$, and $1040$ is divisible by $11$ iff $104$ is divisible by $11$ (using (2)), which it is not.

Next $1007$ is divisible by $13$ iff $1020$ is divisible by $13$ iff $102$ is divisible by $13$, which it is not.

Next $1007$ is divisible by $17$ iff $1007-17=990$ is divisible by $17$ iff $99$ is divisible by $17$, which it is not.

Next $1007$ is divisible by $19$ iff $1007-19\cdot 3=950$ is divisible by $19$ iff $95$ is divisible by $19$, which it is.

We've found a factor of $1007$, namely $19$. In fact, $1007=19\cdot 53$.

Note: This method looks long when written out, but with practice, it does allow for mental determination of divisibility by small numbers quite quickly and efficiently.

Answer 2

Here's an unusual yet effective technique for factoring.

Since (A² - B²) = (A + B)(A - B), if you can express the given number as the difference between 2 perfect squares, you can factor numbers up to 3000. I use the following technique for numbers up to 10,000 myself.

Consider that perfect squares only have a few possible endings. Perfect squares can only end in 0, 1, 4, 5, 6, or 9.

As a matter of fact, there are also a limited number of 2-digit endings. If a perfect square ends in 0, it's always going to end in 00. If a perfect square ends in 5, it's always going to end in 25. Here are the remaining possibilities for the last 2-digits of perfect squares:

1: 01, 21, 41, 61, 81
4: 04, 24, 44, 64, 84
6: 16, 36, 56, 76, 96
9: 09, 29, 49, 69, 89

When given a number m to factor, take a look at the last 2 digits of m, and put it into 1 of 3 categories. If m ends in 1 or 9, you'll use approach 1 or 2. If it ends in 3 or 7, you'll use the 3rd approach.

---

1. Are the last 2 digits of m the ending of a perfect square?

If so, then there are two possibilities for (A² - B²):

The first possibility is that A² ends in the same 2 digits as m, and B² ends in 00.

Example of this case: 341 ends in 41, and there are squares which end in 41, so we could factor 341 by starting with squares ending in 41 and subtracting numbers in the hundreds. (In fact, 341 = 441 - 100, or 21² - 10², so the factors of 341 are 31 (21 + 10) and 11 (21 - 10).

The second, and only other possibility in this case, is that A² ends in 25, and B² ends in ((125 - last two digits of m) mod 100).

Example of this case:  341 ends in 41, and there are squares which end in 41, so we could factor 341 by starting with squares ending in 25 and subtracting squares ending in 84 (84 = (125 - 41) mod 100). As it turns out, this approach doesn't actual give us any useful differences of squares for 341, but it can work in other cases.

---

2. Are the last 2 digits of m a complement of the last 2 digits of a perfect square? (In other words, could m plus a perfect square be made to add to a multiple of 100?)

If so, then there are two possibilities for (A² - B²) in this case, as well:

The first possibility in this case is that A² ends in 00, and B² ends in the 2 digits that complement m.

Example of this case: 679 ends in 79, but no perfect square ends in 79. However, 79 is a complement of 21, and there are squares ending in 21. So, we could factor 679 by trying out an A² that ends in 00 and a B² that ends in 21.

The second, and only other possibility in this case, is that A² ends in (last 2 digits of m + 25) and B² ends in 25.

Example of this case: 679 ends in 79, but no perfect square ends in 79. However, 79 is a complement of 21, and there are squares ending in 21. So, we could factor 679 by trying out an A² that ends in 04 (since 79 + 25 ends in 04) and a B² that ends in 25.

---

3. Is the units digit of m a 3 or a 7?

If so, you'll have quite a few numbers to try out, but we can still limit the possibilities.

If m ends in 03, 23, 43, 63, or 83, then the units digit of A² must be a 4 and the units digit of B² must be a 1.

If m ends in 07, 27, 47, 67, or 87, then the units digit of A² must be a 6 and the units digit of B² must be a 9.

If m ends in 13, 33, 53, 73, or 93, then the units digit of A² must be a 9 and the units digit of B² must be a 6.

If m ends in 17, 37, 57, 77, or 97, then the units digit of A² must be a 1 and the units digit of B² must be a 4.

---

These rules can help limit at which numbers you consider for (A² - B²), but you still have to work through the numbers. Your minimum starting point for A is ⌈sqrt(m)⌉, and you only need to consider numbers equal to or greater than that with the qualities as determined above.

Let's try factoring this way with your example number, 1007. ⌈sqrt(1007)⌉ = 32, so 32 is the lowest number we should consider for A.

Since it ends in 07, A² must end in 6, and B² must end in 9. For A² to end in 6, A must end in either a 4 or a 6. For B² to end in 9, B must end in either a 3 or a 7.

So, the series of numbers we need to test for A are limited to 34, 36, 44, 46, 54, and so on.

34² = 1156, and 1156 - 1007 = 149. 149 is not a perfect square.

36² = 1296, and 1296 - 1007 = 289. Wait! 289 is a perfect square! It's 17²!

So, 1007 = 1296 - 289. This means that 1007 = (36² - 17²) = (36 + 17)(36 - 17) = 53 × 19.

There are a few other patterns that can help limit your search in some cases.

If you consider the first 4 perfect squares as the 2-digit numbers 00, 01, 04, and 09, then every possible 2-digit ending of a perfect square shows up in a list of the first 25 perfect squares.

Also, when you're dealing with one of the first 2 situations, and you find A² or B² needs to have a specific 2-digit ending, work out which perfect square of the numbers 1 through 25 has that 2-digit ending.

For example, if you need squares that end in 24, the only number from 1 to 25 whose square ends in 24 is 18 (when squared, it's 324).

Once you've found a number like this, you only need to look at numbers which are that distance from a multiple of 50!

In our example where we needed a number ending in 24, we found that 18 squared gives a number ending in 24. This tells us that the squares ending in 24 will all be 18 away from a multiple of 50. In other words, the only numbers that, when squared, will have a 2-digit ending of 24 will be 18, 32, 68, 82, 118, and so on.

As a final example, let's try and factor 679 with this approach. ⌈sqrt(679)⌉ = 27, so 27 is the lowest number we should consider for A.

No squares end in 79, but 79's complement is 21, so we can use the approaches from the second technique above. So, A² either ends in 00, or it ends in 04.

For A² to end in 00, A would have to be a multiple of 10. For A² to end in 04, A would have to be 2 numbers away from a multiple of 50: 2, 48, 52, 98, 102, and so on.

Starting from 27, the first possibility to try is 30², or 900. 900 - 679 = 221, and 221 is not a perfect square.

Next, let's try 40² (1600). 1600 - 679 = 921, which is not a perfect square.

What about 48² (2304)? 2304 - 679 = 1625. Again, this is not a perfect square.

50², or 2500, is next on our list. 2500 - 679 = 1821. Nope, no perfect square here, either.

52² is 2704, and 2704 - 679 = 2025, which is a perfect square!

So, 679 = (2704 - 2025) = (52² - 45²) = (52 + 45)(52 - 45) = 97 × 7.

Yes, this approach can take a while, but at least you limit your tries. You can always stop trying possibilities at ⌈(m/2)⌉, as the only possibility at that point is that A and B differ by 1, and every number has 1 as a divisor.

For example, 1007 can be factored as (504² - 503²), but since this works out as (504 + 503)(504 - 503) = 1007 × 1, this doesn't tell us anything really useful.