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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: