Murad’s Divisibility Test

Murad A. AlDamen

https://www.angelfire.com/de2/abbas

dinvisibility@yahoo.com

 

 Acrobat reader 

Abstract

A general divisibility test for integers is given and proven.

ملخص

يقدم هذا البحث طريقة جديدة بسيطة و عامة لاختبار قابلية قسمة عدد على آخر مع برهان لهذه الطريقة.

 

INTRODUCTION

Divisibility for integers and it tests are important in number theory and cryptography.

There are many tests of divisibility, different for different integers no general test for divisibility of any integer N by any integer M . Below is a list of famous divisibility tests for the given integers.

 

A prime	Divisibility test of N by the prime
2	If N is an even (that is the say if rightmost digit of N is Zero or an even digit) then 2 divides N.
3	If the sum of the digits of N is divided by 3 then N is divided by 3.
5	If the rightmost digit of N is 0 or 5 then 5 divides N.
7	Double the units and substract from the tens; it the chain ends in zero or a multiple of 7 then the original number is divisible by 7;e.g.: 1365136-2*512612-2*6=0.
11	Let N = a1a2a3…ak then if (a1a2+a3a4+…) is divided by 11 then N is divided by 11. Substract the units from the terms, if the chain ends in zero then the original number is divisible by 11.
13	Add the terms to 4 times the units; if the chain ends in a multiple of 13 then the original number is divisible by 13.
17	Substract the last two digits from twice the hundreds, and so on, if it ends with a multiple of 17, then it is divisible by 17.
19	Add the hundreds less to 4 times the rest, if the chain ends in a multiple of 19, then the original number is divisible by 19.
	…

 

This paper is concerned with giving a general test. We shall find conditions that make the integer N divide by the number M.

Symbol List:

M, N are positive integers, M ≤

L is a positive integer that satisfies LM =N

n₁ the units of N

n₂ the tens of N , n₁+10n₂=N

m₁ the units of M

m₂ the tens of M, m₁+10m₂=M

 

Test 1:

 

M|N n₂m₁m₂n₁  (mod M); where m₂m₁ & m₂0

Proof:

Assume M|N L integer, L

M.L=N

L (m₁+10m₂)=(n₁+10n₂) where M= m₁+10m₂, N= n₁+10n₂

Lm₁-n₁=10(n₂-Lm₂)=10a                                              …(1)

Alson₂-Lm₂=a                                                                       …(2)

Add (1) to (2)

Lm1-n1=10a   n2-Lm2=    a (n2-n1)-L(m2-m1)=11a

 

But ML=N

(m₁+10m₂)(n₂-n₁)-(n₁+10n₂)(m₂-m₁)=

n₂m₁-m₁n₁+10m₂n₂-10m₂n₁-n₁m₂+n₁m₁-10n₂m₂+10n₂m₁

11m₁n₂-11n₁m₂=M (11a)

m₁n₂-m₂n₁=M.a or by congruence language

M|N n₂m₁m₂n₁  (mod M)

Assume n₂m₁m₂n₁  (mod M)

             n₂m₁m₂n₁+kM, k integer ….1

 n₂m₁-m₁n₁+10m₂n₂-10m₂n₁-n₁m₂+n₁m₁-10n₂m₂+10n₂m₁=kM

Or (m₁+10m₂)(n₂-n₁)-(n₁+10n₂)(m₂-m₁)=kM

M (n₂-n₁)-N (m₁-m₂)=kM

(n₂-n₁)+(m₁-m₂)=kM           …2

So (1) to be integral formula the N/M =integer say L i.e. M|N

q.e.d.

Test 2:

Let x be an integer if:

1)

2) m₂0 and m₁m₂

Then M|N

Proof:

, m₂0

(m₁(n₂-x)-n₁m₂)10xm₂+Mkm₂,      k integer

m₁n₂-n₁m₂10xm₂+m₁x+Mkm₂    but  M=m₁+10m₂

m₁n₂-n₁m₂xM+Mkm₂0 (mod M)     

q.e.d.

Example 1:

N=3598207

M=61

N is divided by M because 3598207/61=58987

n₁=7, n₂=359820

m₁=1, m₂=6

Murad’s Divisibility Test or (MDT): m₁n₂n₁m₂ (mod M)

359820*16*7=359778

359778=N, 61=M

n₁=8, n₂=3597735977*16*8=35929 …and so on and so for …30*16*5=0;  

the zero is divided by 61 then M|N.

 

Example 2:

M=7: m₂=03*7=21 to avoid m₂=0

  m₂=2; m₁=1n₂-2n₁0 (mod 7)

 

Example 3:

M=11; m₂=m₁ but Murad’s divisibility is right for 11 m₂=1, m₁=1

n₂-n₁0  (mod 11)

 

Conclusion

In this paper I’ve presented a new general method to test any integer if is divisible by any integer else.

Divisibility tests are important in number theory and cryptography.

Until now there is no general divisibility test for any prime number or also I’ve presented a complete proof for this test.

References

[1] "Divisibility Tests" by A. Khare, Furman University Electronic Journal of Undergraduate

      Mathematics, Volume 3, 1997, pp 1-5.

[2] "Tests for divisibility by 19" by M. Humphreys and N. Macharia, The Mathematical Gazette, Vol

      82, No. 495, November 1998, pp 475-477.

[3] Burton, D. M. "Special Divisibility Tests." §4.3 in Elementary Number Theory, 4th ed. Boston,

      MA: Allyn and Bacon, pp. 89-96, 1989.

[4] Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York:

      Chelsea, pp. 337-346, 1952.

[5] Gardner, M. "Tests of Divisibility." Ch. 14 in

     The Unexpected Hanging and Other Mathematical   Diversions. Chicago, IL: Chicago University

     Press, pp. 160-169, 1991.

[6] Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England:

       Penguin Books, p. 48, 1986.

[7] Carlos Rivera Website http://www.primepuzzles.net/