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,

.

### Like this:

Like Loading...

*Related*

## Leave a Reply