Multiplying 3 numbers at once to find age in seconds at 21 years

Is there a quick way to find factors of a number?

Last updated: August of 2006
Level 2 update on Mar 26, 2007 - divisibility trick for 11 added thanks to an E-mail submission

Type:              Trick and shortcut
Reliability:        - High
Ease of learning:   - Easy-medium
Time saving:        - Small gain
Usefulness:         - Somewhat useful
Difficulty:         - Easy-medium
Overall:            - Good

1 Determining divisibility

1.1 The basics

Consider this question:

List all denominators a fraction with a denominator of 3000 would have, when reduced.

This may sound hard, but there's a way to guarentee that you can find them all. Start with the lowest prime number, 2. Since the last digit is an even number, it is divisible by two. Take 3000 and divide by two:

Since two is already a factor, then you can use 1500.

Now check for three. To find three, add the digits of the number together. If the added values add to a multiple of 3, in which 3+0+0+0=3, 3000 is a multiple of 3. You'd get 1000 as the other number. For 4, you check to see if the last two digits, the ones and the tens, are a multiple of 4. If it ended in, for example, 1368, it would be based on 68, and 68 is a multiple of 4. If it was 3754, it wouldn't be as 54÷4=13.5, which means it doesn't come out evenly. 3000 is a multiple of 4 as 0 is a multiple of four. Doing the division, you get 750. For five, which should be easy, the number should end in either a 5 or a 0. 3000 ends in a zero so it is a multiple of 5. 600 is the other number. Now, for multiples of six, you'd apply the same principal as 3, except the number must be even. 3000 is a multiple of 3, and it is even, so it is a multiple of 6. 500 is the other number. 7 is a real challenge. I don't know of a trick to tell if a number is a multiple of 7 or not. However, if you divide it, it doesn't come out evenly:

3000 is not a multiple of 7, thus it wouldn't be a multiple of anything else based on that. For 8 though, it does. To find multiples of 8, the last 3 digits must be a multiple of 8. 0 is a multiple of 8 so it is good. 375 is the other number you get when you divide.

To find multiples of 9, Do the same as you did for 3's, except the sum should be a multiple of 9. 3 is not a multiple of 9, thus 3000 isn't a multiple of 9. For ten, in which you should know, the last digit must be a zero. 300 is the other one. For 11, every other digit must be added then those left out added in a separate sum. If the difference between these sums is a multiple of 11, the number given is a multiple of 11. 3000 has 3 and 0 and the difference, 3, is not a multiple of 11 so 3000 is not a multiple of 11**. For 12, it must meet two conditions: the last two digits are a multple of 4 and the digits add up to a multiple of 3. 3000 meets both so it is a multiple of 12. The other number is 250. There's no known strategy for screwball 13, but apply the same method as 7. Since 14 is a multiple of 7 and 3000 isn't a multiple of 7, 14 definitely wouldn't go in. 15 works under the following conditions: digits add up to a multiple of 3 and the last digit must be either a 5 or a 0. 3000 meets both. 200. This just continues on until you come to the square root of the number. For the complete list, the answer to the question in focus would be:

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 25, 30, 40, 50,
60, 75, 100, 120, 125, 150, 200, 250, 300, 375, 500, 600, 750, 1000, 1500, 3000

Yow! 3000 has a ton of factors! Note: I split the list in two groups. The last on the top is where you would not get anything new. The square root of 3000 is about 54 3/4 (mental estimate) as 55^2 is 3025 (exact; using the same-number trick as a guide).

1.2 A chart to help out

This chart will summarize the basics of determining visibility in a more organized form. This relates to whole numbers only, not fractions (except the numerator and/or denonimator individually, not as a whole) or decimals.

1	Always divisible	2	Must be even
3	All digits add up to a multiple of 3	4	Last two digits must be a multiple of 4
5	Must end in 5 or 0	6	Both rules of the 2 and 3 must match
7	No known technique	8	Last 3 digits must be a multiple of 8
9	Same as 3, except they must add up to a multiple on 9 instead	10	Must end in a zero
11	Difference of alternating digits' sums must be multiple of 11**	12	Both rules of the 3 and 4 must match
13	No known technique	14	No known technique (due to 7)
15	Both rules of the 3 and 5 must match	16	Last 4 digits must be a multiple of 16
17	No known technique	18	Both rules of the 2 and 9 must match
19	No known technique	20	Last digit must be a zero and the digit to the left must be even.
21	No known technique (due to 7)	22	Both rules of the 2 and 11 must match
23	No known technique	24	Both rules of the 3 and 8
25	Last two digits must end in 00, 25, 50, or 75.	26	No known technique (due to 13)
27	No known technique*	28	No known technique (due to 7)
29	No known technique	30	Both rules of the 3 and 10 must match
31	No known technique	32	The last 5 digits must be a multiple of 32.
33	Both rules of the 3 and 11 must match	34	No known technique (due to 17)
35	No known technique (due to 7)	36	Both rules of the 4 and 9 must match
37	No known technique	38	No known technique (due to 19)
39	No known technique (due to 13)	40	Both rules of the 5 and 8 must match
41	No known technique	42	No known technique (due to 7)
43	No known technique	44	Both rules of the 4 and 11 must match
45	Both rules of the 5 and 9 must match	46	No known technique (due to 23)
47	No known technique	48	Both rules of the 3 and 16 must match
49	No known technique (due to 7)	50	Last two digits must end in 00 or 50.

* If you used a different base, it might work with adding up the digits and, like 3 and 9, be a multiple of 27 (knowning the pattern). This is unconfirmed.
** What I mean by this is that, take 397,529 as an example. Adding 3+7+2 gives 12. Note the alternating digits. Repeat for those left out, or 9+5+9, or 23. The difference between 23 and 12 is 11 and since 11 is a multiple of 11, the number 397,529 is a multiple of 11**.

2 An even faster way

2.1 The faster way

There's an even faster way to find all the factors! Consider 3000 again. Divide it by 2 if possible. 1500. If it divides evenly, keep repeating until you get a fraction: 750, 375, 187.5. Ignore the fraction one and stop where you last had an even number, 375. Now divide by 3 in the same fashion. 125, 41.66666.... Stop at 125. Next, skip 4 as four is not a prime number, and go to 5 and repeat: 25, 5, 1, .2. Once a value ends in 1, you've found all prime factors. Just multiply these to get all of your divisibilities. The list is 2, 2, 2, 3, 5, 5, then another 5. Let's try a much more complex number: 2339. It's not an even number so don't consider 2. It doesn't end in 5 or 0 so it's not a 5 eihter. The digits add up to 17, not a multiple of 3. The next prime number is 7. Doing the division, it doesn't come out. 9 has 2 3's, so it's not prime but 11 is. For 11, the sums are 5 and 12 and the difference, 7, is not a multiple of 11 and thus not a multiple of 11. You continue to 13, then 17, 19, 23, etc.. When you divide by about 47, and still haven't taken anything out of it, and if the next prime number, 53, crosses over your last result, you don't need to continue. If this happens, you've found a prime number.

2.2 Prime numbers up to 100

Here is a list of all prime numbers up to 100. A prime number is a number with only two factors: 1 and itself.

02  03  05  07  11
13  17  19  23  29
31  37  41  43  47
53  59  61  67  71
73  79  83  89  97

3 List of HUGE prime numbers

I've got quite a list of prime numbers, even some 6-digit and 7-digit prime numbers following this method! The prime numbers above 20,000 required the help of a MSWorks or Excel spreadsheet to get them for sure. I was bored and I was playing a game I call "factors" and that's how I came across these. Here's the list of big ones I've found:

These are actual prime numbers that I've got from playing the game "factors" that I so enjoy^*.

Footnotes:
* This game features what is described in section 2.x above. This game is easy to play, and you can learn how here.
** This trick was submitted to me via E-mail. Credit goes to him/her who submitted it.

[an error occurred while processing this directive]