Suppose you want to figure out (without computing aid) if a number (which is not too large) is prime. Many people are unaware that it suffices to check for prime factors up to . This is because factors of come in pairs: and . Since we have two numbers multiplying to the smaller factor must be at most :
A second tip is that to check whether a prime is a factor of , instead of dividing by it helps to add or subtract multiples of to reach a multiple of . Then check whether this new number divided by is a multiple of . 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 is prime. It is possible for each line to be performed mentally. I only use divisibility “tricks” for the cases of . It also helps to know that is a multiple of . We need to check primes up to , since .
- 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.
- (summing alternating digits), so 2011 is not divisible by 11.
- 2011 is divisible by 13 iff 2011-13 = 1998 is, but 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 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 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 is prime! You might want to try a similar exercise to show is also prime.
Finally, note that if the original number is less than , then one only needs to check primes up to , and remember the following special cases involving higher factors:
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,