-----------------------------------
Divisibility Rules By Prime Numbers
-----------------------------------
We only need to Divisibility by prime numbers because if a number is divisible by
one or more prime numbers, then it is also divisible by the number composed by multiplying these primes.
Ex: Because 24 is divisible by 2 and 3, then it is also divisible by  6 so no need to test it for divisibility by 6.

-----------------------------------------
Is 1 a Prime Number?                   NO
Is 2 a Prime Number?                  YES
Is 9 a Prime Number?                   NO
-----------------------------------------

# 1 is the Unit
  1 is the father of all numbers

# Primes are the mothers of their multiples.
  Ex: 2 is the mother of half of the numbers

# Composites are kids of their mothers.
  Ex: 6  has two mothers, 2 and 3.
  Ex: 9  has two similar mothers, 3 and 3.
  Ex: 12 has three mixed mothers, 2, 2 and 3.

In chemistry, the number of protons determines which chemical element an atom is.
So 1 to mathematics is like the proton to chemistry. It detemines what number a value is.
Ex: 1+1+1+1+1 = 5

In chemistry, atoms of similar or different types make up molecules.
So primes to mathematics are like atomes to chemistry. They generate their composites.
EX: 2 * 2 * 3 = 12       where 2, 2, and 3 are the prime multipliers.

  Here is a list of the first few prime numbers:
  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
  ... infinity

In chemistry, molecules are made from similar or different types of atoms.
So composites to mathematics are like molecules to chemistry. They are generated by their prime factors.
EX: 2 * 2 * 3 = 12       where 12 is the composed result.

  Here is a list of few composite numbers:
  4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39
  40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69
  70, 72, 74, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 100,
  ... infinity

NOTE:
Even and odd numbers are only a special case of numbers that are divisible by the first prime (2)
In general, evens should be written as even2 and odds as odd2.
This way we can have even3/odd3, even5/odd5, ... evenP/oddP for any P prime number.

Ali Adams
www.heliwave.com
God >




--------------------------------------------
Divisibility Rule for Prime Numbers below 50
© Stu Savory, 2003 & 2004.
--------------------------------------------

Divisibility by 2
A number is divisible by 2 if its last digit is even (0, 2, 4, 6 or 8). 

Divisibility by 3
A number is divisible by 3 if the sum of its digits is divisible by 3 too.
Ex: 534: 5+3+4=12 and 1+2=3 which is divisible by 3 so 534 is divisible by 3. 

Divisibility by 5
A number is divisible by 5 if the last digit is 5 or 0. 

Divisibility by 7     (-2)
Double the last digit and subtract it from the remaining leading truncated number.
If the result is divisible by 7, then so was the original number.
Apply this rule over and over again as necessary.
Ex: 826--> 82-2*6 =70 which is 10*7 so 826 is divisible by 7. 

Divisibility by 11     (-1)
Subtract the last digit from the remaining leading truncated number.
If the result is divisible by 11, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 19151--> 1915-1 =1914 -->191-4=187 -->18-7=11, so yes, 19151 is divisible by 11. 

Divisibility by 13     (+4)
Add four times the last digit to the remaining leading truncated number.
If the result is divisible by 13, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 50661-->5066+4*1=5070-->507+4*0=507-->50+4*7=78-->7+4*8=39 which is 3*13, so 50661 is divisible by 13. 

Divisibility by 17     (-5)
Subtract five times the last digit from the remaining leading truncated number.
If the result is divisible by 17, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 3978-->397-5*8=357-->35-5*7=0. So 3978 is divisible by 17. 

Divisibility by 19     (+2)
Add two times the last digit to the remaining leading truncated number
If the result is divisible by 19, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 101156-->10115+2*6=10127-->1012+2*7=1026-->102+2*6=114 which is 6*19, so 101156 is divisible by 19. 

Divisibility by 23     (+7)
Add 7 times the last digit to the remaining leading truncated number.
If the result is divisible by 23, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 17043-->1704+7*3=1725-->172+7*5=207 which is 9*23, so 17043 is also divisible by 23. 

Divisibility by 29     (+3)
Add three times the last digit to the remaining leading truncated number.
If the result is divisible by 29, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 15689-->1568+3*9=1595-->159+3*5=174-->17+3*4=29, so 15689 is also divisible by 29. 

Divisibility by 31     (-3)
Subtract three times the last digit from the remaining leading truncated number.
If the result is divisible by 31, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 7998-->799-3*8=775-->77-3*5=62 which is 2*31, so 7998 is also divisible by 31. 

Divisibility by 37     (-11)
Subtract eleven times the last digit from the remaining leading truncated number.
If the result is divisible by 37, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 23384-->2338-11*4=2294-->229-11*4=185 which is 5*37, so 23384 is also divisible by 37. 

Divisibility by 41     (-4)
Subtract four times the last digit from the remaining leading truncated number.
If the result is divisible by 41, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 30873-->3087-4*3=3075-->307-4*5=287-->28-4*7=0 which is 0*41, so 30873 is also divisible by 41. 

Divisibility by 43     (+13)
Add thirteen times the last digit to the remaining leading truncated number.
If the result is divisible by 43, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 3182-->318+13*2=344-->34+13*4=86 which is 2*43, and so 3182 is also divisible by 43. 

Divisibility by 47     (-14)
Subtract fourteen times the last digit from the remaining leading truncated number.
If the result is divisible by 47, then so was the first number.
Apply this rule over and over again as necessary. 
Ex: 34827-->3482-14*7=3384-->338-14*4=282-->28-14*2=0 which is 0*47, so 34827 is divisible by 47. 


--------------------------------------------------------------------------------------------------
Is N divisble by P?
# Find the minimum x to multiply by P to produce a number ending with 1 or 9.
# If zzz9, then M = +zzz + 1
# If zzz1, then M = -zzz
# then loop continuously siplit the number into front digits and 1 rear digit
  N = f + M*r     where f=front digit(s) and r=rear digit
  until f is divisible by P, then N is divisible by P,
  or if f is indivisible by P, then N is indivisible by P.

Ex: Is 126293 divisible by 17
What is the minimum x to multiply by 17 to produce a number ending with 1 or 9?
Answer: x = 3 as 3*17 = 51 = zzz1
Number ends in 1 so SUBTRACT the zzz digit(s) which is 5 in this case
so M = -zzz = -5

So lets split 126293 into f=12629 and r=3 and loop continuoisly until we get a number divisible or indivisible by 17:

126293
12629 and 3*-5 = -15
  -15
12614
1261  and 4*-5 = -20
 -20
1241
124   and 1*-5 = -5
 -5
119
11    and 9*-5 = -45
-45
-34
+3    and 4*-5 = -20     [-3 becomes +3 disregarding the sign]
-20
-17     is divisible by 17 so 126293 is divisible by 17 too :)

Checking by calculator indeed 126293 / 17 = 7429 without remainder.


Summary:
We have displayed the recursive divisibility test of number N as f-M*r 
where f are the front digits of N, r is the rear digit of N and M is some multiplier.
And we want to see if N is divisible by some prime P. We need a method to work out the values of M.
What you do is to calculate (mentally) the smallest multiple of P which ends in a 9 or a 1. 
If it's a 9 we are going to ADD the leading number of the multiple plus 1 as our M.
If it's a 1 we are going to SUBTRACT the leading number of the multiple as our M.

So for P=17: three times 17 is 51 which is the smallest multiple of 17 that ends in a 1 or 9.
Since it's a 1 we are going to SUBTRACT later.
The leading digit of 51 is a 5, so we are going to SUBTRACT five times the remainder r.

----------------------------
THE PROOF
----------------------------
Let N = 10f + r  [f=front digits, r=rear digit]

Multiply both sides by M = -5 [for P=17]:

-5N = -50f -5r

Add 51f to both sides 
[because 51 is the smallest multiple of P=17 to produce a result ending in 1 or 9]

51f - 5N = 51f - 50f - 5r
51f - 5N =         f - 5r


If N is divisible by P (here P=17) then factor P out of N = P*x:

51f   - 5*17x  = f - 5r
17*3f - 17*5x  = f - 5r

17 * (3f - 5x) = f - 5r

therefore        f - 5r is a multiple of 17.

Q.E.D. 
--------------------------------------------------------------------------------------------------


Ali Adams
www.heliwave.com
God >
