# Mentally finding factors of an integer of up to three-digits.

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.

• 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. – YukiJ May 11 '18 at 10:58
• @YukiJ The OP wants to find factors, not necessarily prime. For instance, 6 is a factor. – scaaahu May 11 '18 at 11:35
• @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. – YukiJ May 11 '18 at 11:37
• @YukiJ Having a factor 9 implies having a factor 3, not the other way around. – scaaahu May 11 '18 at 11:52
• @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. – YukiJ May 11 '18 at 11:55

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$

• Thanks for your answer, which I’ve up-voted. I’ve used a similar method with numbers such as $721$. – Old Peter May 11 '18 at 14:42
• 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$. – Rhys Hughes May 11 '18 at 14:56