# Chaitanya's Random Pages

## April 21, 2012

### Divisibility tips

Filed under: mathematics — ckrao @ 8:17 am

Suppose you want to figure out (without computing aid) if a number $n$ (which is not too large) is prime. Many people are unaware that it suffices to check for prime factors up to $\sqrt{n}$. This is because factors of $n$ come in pairs: $a$ and $n/a$. Since we have two numbers multiplying to $n$ the smaller factor must be at most $\sqrt{n}$:

$\displaystyle n = a.(n/a) \geq \left(\min\{a,n/a\}\right). \left(\min\{a,n/a\}\right) = \left(\min\{a,n/a\}\right)^2.$

A second tip is that to check whether a prime $p$ is a factor of $n$, instead of dividing $n$ by $p$ it helps to add or subtract multiples of $p$ to reach a multiple of $10$. Then check whether this new number divided by $10$ is a multiple of $p$. The key idea is that we are not interested in the quotient, only that the remainder is non-zero.

For example here is how I would determine whether $2011$ is prime. It is possible for each line to be performed mentally. I only use divisibility “tricks” for the cases of $2,3,5,11$. It also helps to know that $111$ is a multiple of $37$. We need to check primes up to $43$, since $45^2 = 2025$.

• It ends in 1, so it is divisible by neither 2 nor 5.
• Its digit sum is 4 so it is not divisible by 3.
• 2011 – 21 = 1990, 199 is not divisible by 7 since 210 (11 away) is.
• $2 + 1 \neq 0 + 1$ (summing alternating digits), so 2011 is not divisible by 11.
• 2011 is divisible by 13 iff 2011-13 = 1998 is, but $1998 = 2 \times 999 = 2 \times 111 \times 9$ does not have 13 as a factor (111 is 19 away from 130).
• 2011 – 51 = 1960, but 196 is not divisible by 17 since 170 (26 away) is.
• 2011 + 19 = 2030, but 203 is not divisble by 19 since 190 (13 away) is.
• 2300 – 2011 = 289, 289 – 230 = 59, which is not divisible by 23, hence 2011 is not divisible by 23.
• 2011 + 29 = 2040, 204 is not divisible by 29 since $203 = 7 \times (30 - 1)$ is.
• 2011 – 31 = 1980, 198 is not divisible by 31 since 186 (12 away) is.
• 2011 is not divisible by 37 since 1998 (13 away) as found above is $2 \times 111 \times 9 = 2 \times 37 \times 3 \times 9$ is.
• 2011 – 41 = 1970, 197 is not divisible by 41 since 205 is.
• 2011 + 129 = 2140, 214 is not divisible by 43 since 215 is.

Hence $2011$ is prime! You might want to try a similar exercise to show $2003$ is also prime.

Finally, note that if the original number is less than $1072$, then one only needs to check primes up to $23$, and remember the following special cases involving higher factors:

• $841 = 29^2$
• $899 = 30^2 - 1 = (30 + 1)(30-1)$
• $961 = 31^2$

How does 1073 factorise? If one has a suspicion that it has large factors, one can find a square just larger and then if one gets lucky use the difference of squares formula. Indeed here,

$\displaystyle 1073 = 1089 - 16 = 33^3 - 4^2 = (33 - 4)(33 + 4) = 29 \times 37$.