1
$\begingroup$

I’m looking for the easiest methods to find factors, not necessarily prime, of positive integers $<1000$, preferably mentally, but using pen and blank paper when required.

Although these techniques might be useful for a certain televised Numbers Game, I’m just looking for methods faster than trial division.

I take for granted full knowledge of the twelve by twelve multiplication tables, and recognition of primes up to $101$

This, with the addition of $7\cdot13=91$ should cover much of the factorisation up to two digits.

Notation Using the idea of hundreds, tens and units, so $n=100H+10T+U$ is the number, I’ll use $H,T,U$ for the individual digits, $HT$ for the first two digits and $TU$ for the last two.

For example, $n=456$ gives $H=4$, $T=5$, $U=6$, $HT=45$ and $TU=56$

Some easy published divisibility tests

If $U=0$ then $10|n$

If $(TU)\equiv 0{\pmod{25}}$ then ${25}|n$

If $U=5$ then $5|n$

If $U\equiv 0{\pmod 2}$ then $2|n$

If $(H+T+U)\equiv 0{\pmod 9}$ then $9|n$

If $(H+T+U)\equiv 0{\pmod 3}$ then $3|n$

Merged published divisibility tests for primes $p=7$ to $47$

With $z$ taken from the following, if $(HT+zU)\equiv 0{\pmod p}$ then $p|n$

$$(p,z)$$ $$(7,-2)$$ $$(11,-1)$$ $$(13,4)$$ $$(17,-5)$$ $$(19,2)$$ $$(23,7)$$ $$(29,3)$$ $$(31,-3)$$ $$(37,-11)$$ $$(41,-4)$$ $$(43,13)$$ $$(43,-30)$$ $$(47,-14)$$

For some examples in the range, the test may need to be repeated on the result.

As $31^2=961$, the last few test are of limited use.

Alternative divisibility test for $11$

If $(H+U-T)=0$ or $11$ then $11|n$

Difference of two squares

Using $a^2-b^2\equiv(a+b)(a-b)$ helps in a few cases. For example,

$$899=900-1=(30+1)(30-1)=31\cdot29$$

$$91=100-9=(10+3)(10-3)=13\cdot7$$

$$391=400-9=(20+3)(20-3)=23\cdot17$$

My question

I was tempted to ask what other divisibility or factorisation techniques exist that are potential easier than trial division, but “easier” is subjective; so I questions is:.

What other mental divisibility or factorisation techniques exist for an integer up to three digits?

Clarification update 11 May 2018

Sorry, I don’t feel I’ve sufficiently emphasised the importance of time, just assuming that easier was faster.

Full factorisation is ideal; partial factorisation is much better than nothing, so $663=3\cdot13\cdot17$ is best, but $663=3\cdot221$ is better than nothing.

Obtaining more than one small prime factor with one test is desirable, where the prime factors are obvious, as per the tests for $10,25$ and $9$, but a full list of all possible factors of $n$ is not needed.

$\endgroup$
  • 2
    $\begingroup$ For three digit numbers you only have to do 11 trial divisions to find factors (for the primes from 2 up to 31). If none of them divides your number, no number does (except 1 and the number itself, of course). Trial divisions for 2,3,5,7 and 11 are easy. $\endgroup$ – YukiJ May 11 '18 at 10:58
  • $\begingroup$ @YukiJ The OP wants to find factors, not necessarily prime. For instance, 6 is a factor. $\endgroup$ – scaaahu May 11 '18 at 11:35
  • $\begingroup$ @scaaahu Yes, but if we observe that 2 and 3 are factors in a number then their product $2\cdot 3 =6$ is necessarily also a factor. Hence, if you find the prime factors, you also found the remaining other factors. $\endgroup$ – YukiJ May 11 '18 at 11:37
  • $\begingroup$ @YukiJ Having a factor 9 implies having a factor 3, not the other way around. $\endgroup$ – scaaahu May 11 '18 at 11:52
  • $\begingroup$ @scaaahu True but if you know that 3 divides $n$ then you can also check if 3 also divides $n/3$. If so, 9 divides $n$. In the particular case with 9 you could even check if the sum of digits of $n$ is divisible by 9. $\endgroup$ – YukiJ May 11 '18 at 11:55
1
$\begingroup$

As you have stated:

Checking a number is even will automatically give you the factor of $2$.

Summing the digits, if the digit sum is a multiple of $3$ or $9$, the number is also a multiple of $3$ or $9$.

Multiples of $5$ end in $5$, multiples of $10$ end in $0$.


For my extra method, let's consider $473$. It has no obvious factors based on those rules, so here I would use prime multiple subtraction. Start with $7$, the multiple of $7$ that ends in $3$ is $7\cdot9=63$, so subtract $63$ to get $410$. $41$ is not a multiple of $7$ or $9$, so neither are factors. Then consider $11$. $3\cdot 11=33$ so subtract $33$ to get $440$. $440=40\cdot 11$, hence we can see that $473=43\cdot 11$.


Note for $11$ that if you have $ab\cdot11$ , where $a,b$ represent the digits, the result is $a(a+b)b$, again to mean digits: e.g. $35\cdot11=385$. When $a+b>10$, it is harder to spot but still possible. What you should look for then is: $a(a+b-11)b$, and this is $(a-1)b \cdot 11$. E.g. for $528$, $5+8-11=2, \therefore 528=11*48$


If you can identify numbers as concatenations of multiples of the same number, they will be a multiple of that number. E.g. $654$ contains $6$ and $54$, both of which are multiples of $6$, and so we can do $6\div6=1$, and $54\div6=09$, therefore $654\div6=109$

$\endgroup$
  • $\begingroup$ Thanks for your answer, which I’ve up-voted. I’ve used a similar method with numbers such as $721$. $\endgroup$ – Old Peter May 11 '18 at 14:42
  • $\begingroup$ Thanks for the upvote. Note that $721$ is $7\cdot103$, you can see this by the subtraction method, or notice that $7$ and $21$ are both multiples of $7$, and so we can simply divide both by $7$ for $1$ and $03$ and then put these back together. A different example might be $726$, we see $72=12\cdot 6$ and $6=1\cdot 6$, putting back together we get $121$. $\endgroup$ – Rhys Hughes May 11 '18 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.