Tuesday, May 15, 2018

Divisibility by Numbers ending in 1, 3, 7, and 9 - Proofs of the Formulas

Niranjan Ramakrishnan
May 15, 2018

The previous post provided a set of four empirical formulas to ascertain if a number is divisible by a divisor ending in 1, 3, 7 or 9. This post provides a proof for each of the formulas. Many grateful thanks to Dr Ranjan Roy, who was kind enough to indicate how the proof might be evolved, most importantly the difference of 1 from a multiple of 10.

Notation: The vertical bar, '|' is used here to signify divisibility. E.g., x|y means x is divisible by y.

Let's start by setting down a few identities.
:
10 (x)-1(10x+1) = -1             [1]
10(3x+1)-3(10x+3) = 1         [2]
10(3x+2)-3(10x+7) = -1      [3]
10(x+1)-1(10x+9) = 1           [4]

Without losing generality, we can represent the numbers as (10r+ u), (10x + 1), (10x + 3), (10x +7), (10x + 9), etc.

For divisors ending in 1
Proposition:
If (r-m*u)|(10x+1), then (10r+u)|(10x+1).
where m=x.
Proof:
If (r-m*u) | (10x + 1) then 10(r-m*u) | (10x + 1).
i.e., (10r - 10m*u)| (10x + 1), or, (10r-10x*u)| (10x + 1).
i.e., (10r-(10x+1-1)*u)| (10x + 1).
i.e., ((10r+u) - (10x + 1) * u) | (10x + 1).
Since (10x + 1) * u is divisible by (10x + 1), it follows that (10r+u) ,| (10x + 1).
QED

For divisors ending in 3
Proposition:
If (r+m*u)  | (10x + 3) then (10r+u) | (10x + 3)
where m=(3x + 1).
Proof:
If (r+m*u)  | (10x + 3) then (10r+10m*u) | (10x + 3).
Substitution for m gives
(10r +  10(3x + 1) *u)| (10x + 3).
But as shown above,,
10(3x + 1) =  3(10x + 3) +  1.
(10r + (3(10x + 3) + 1)*u) | (10x + 3).
i.e., ((10r+u) +3(10x + 3) * u)) | (10x + 3).
Since 3(10x + 3)*u ) | (10x + 3), it follows that
(10r + u ) | (10x + 3).
QED.

For divisors ending in 7
Proposition:
If (r-m*u) | (10x +7), then (10r + u) | (10x +7), where m =(3x + 2 ).
Proof:
If (r-m*u) | (10x +7), then (10r - 10m*u) | (10x +7).
Substitution for m gives
(10r - 10(3x + 2) *m) | (10x +7).
But as noted above,
10(3x + 2)  = 3(10x +7) - 1.
Making this substitution yields
(10r - (3(10x +7) - 1) *u) | (10x +7).
Rearranging terms,
((10r+u) - (3(10x +7)*u)) | (10x +7).
Since the second term (3(10x +7) * u) | (10x +7),
(10r+u) | (10x +7).
QED.

For divisors ending in 9
Proposition:
If (r+m*u)  | (10x + 9) then (10r+u) | (10x + 9) where m=x+1.
Proof:
If (r+m*u) | (10x + 9), then 10(r+m*u) | (10x + 9).
i.e., (10r +10m*u) | (10x + 9).
Substitution for m gives
(10r + 10(x+1)*u) | (10x + 9).
But, as noted above,
10(x + 1) = (10x + 9) +  1.
Substitution yields
(10r + ((10x + 9) + 1 ) * u) | (10x + 9).
Rearranging terms,
((10r + u ) + (10x + 9)) | (10x + 9).
The second term, is obviously divisible by (10x + 9).
Therefore, so must be the first team.
(10r + u) | (10x + 9).
QED .

1 comment:

Ananda Vardhana said...

Hi Niranjan,

I read thought it but to be frank my math had reduced to doing addition with great difficulty :). So this is indeed Greek and Latin to me. However I think you should send this to your brother.
Dinakar Ramakrishnan (dinakar at caltech.edu)
Number Theory, Automorphic Forms, Algebraic Geometry
Executive Officer
278 Sloan
(626) 395-4348
I have met him and he is a very nice man and he is very intelligent like you, must be running in the blood. He can comment/validate or take this to the next level. He was the one who introduced us to Dr. Hendrik Lenstra of Lieden where we met your sister Sudha Raghunath.
Phone number: (31/0)71 527-7127
Fax number: (31/0)71 527-7101
Email address: hwl@math.leidenuniv.nl
So you see you are all connected to great mathematicians. Send it to them they are all very good people and respond.
best regards
anand