Is a given number divisible?

There are some very simple tests to find a given integer divisible, for instance 180 is divisible by 4, or 21 by 3. We probably did the tests in school but most of us would have forgotten, since we already have forgotten how to add and multiply never mind long division.

You should understand that if N = n1 x n2 is a product of any two numbers it is divisible by both for example say, 24 =2x6 is divisible by 2 and by 6, and by both 3 and 4 as 12=3x4.

It would often be possible to easily establish divisibility without having to do the actual division.

The actual Tests

To be divisible by 2 it must be an even number, which means divisible by 2 and then ending, the last digit is one of 0 , 2 , 4 , 6, or 8. Testing for four, the last two digits must be divisible by 4. You can see this by writing out the multiples of 4, that is, ever fourth number. In the same way if 8 is a factor the last 4 digits the number is a multiple of 8.

-

To see if a number can be divided by 5 is very easy. The last digit must be either 5 or 0. For 10 it has to be divisible by both 2 and 5 since 2x5=10, which gives a last digit of zero, so any such number in our familiar base 10 is simply all the numbers ending in zero. Of course then a number can be divided by 100 if it ends in two zero's etc. These were up to 10, there must be similar tests for further divisors, greater than ten.

-

Three turns out a bit tricky. If  for a given number you add the digits, and  if that sum is divisible by 3, then the original number is too. As, for an example 3 goes into 36, since according to this test, 3+6 in this case is 9, or 93 also, adding the digits is 12, so 3 goes into 36 as well as 93. 

Thus for example take 123321, if we add the digits it is 1+2+3+3+2+1=12 and the digits added up to a whole number which in turn is divisible by 3, then the initial number must be divisible by 3 also. I don't think this is hard to prove, just high school algebra.

A number which is a multiple of both 2 and 3 would be divisible by 6.

We now have tests for 3, as well as for 2 , 4 , 5 , 6 , 8 and 10 divisibility can be seen seen by writing out the multiples.

-

That leaves seven, 7 is a prime number, which by definition means it has no divisors. I don't think there are such tests for dividing by 7 you would have to actually have to go and do the division to establish that.

Prime Numbers

For a number to have divisors it must be some multiple of a prime number, which is not so hard to see. The prime numbers have no divisors so that 2 , 3, 5 , 7 , 11 , 13 , 17 , 19 , 23 etc are prime numbers.

There is a simple algorithm to see if a given number N has no divisors, i.e is a prime number:

For each number N, if none of 2 , 3 , 4 , 5   n , n+1 divides into N (then you may stop at the square root of N since one of the divisors has to be less) then N is a prime. It is ideal for a standard exercise to write the method as a simple computer program.

This test works but can be much refined for instance based on the sieve of Eratosthenes but the given algorithm does work. The mathematicians of Ancient Greece knew this, Euclid also gave an elementary proof that there are infinitely many prime numbers, it is not difficult.

Prime numbers become more and more sparse with increasingly larger numbers, but there is another interesting result, that there is always a prime between any number N and twice that number, that for every integer N is there is always a prime number p with N < p < 2N

Further remarks

The fundamental theorem of arithmetic states that each number can be written out as a product of primes, and in only one way, the factorisation is unique. We have actually assumed this as common sense, it does sound obvious but actually it must be proved from more basic axioms.

These ideas and related results and methods are current and crucial and in even our times, notably those regarding prime numbers, with applications especially in cryptography and computer security, and electronic technology in general.