Divisibility Formula for Numbers Ending in 5  - Proof

Niranjan Ramakrishnan
July 9, 2018

The previous post gave an empirical formula to determine if a number was divisible by a divisor ending in 5. This post offers a proof for the same.

Proposition:
Any number (10r+u) | (10x+5), if (r-x) | n for u=5, or r | n for u=0, where n=(10x+5)/5.

Proof:
If n=(10x+5)/5, n= (2x+1).

Since we're only considering dividends ending in 0 or 5, it is sufficient to show that ((10r+u) / 5) | n.

When u=5, (10r+u) /5 = (2r + 1).
(2r+1) can be rewritten as (2r -2x +2x + 1).
Thus if (r-x) |  n, then (2r + 1) | n, because n=2x+1.
QED.

When u=0, (10r+u) / 5 = 2r.
If r | n, then 2r | n.
QED.

The Divisibility Rule for Numbers ending in 5

Niranjan Ramakrishnan
June 2, 2018

A previous post, Divisibility - A more general approach, provided rules for checking divisibility of a number by any odd number not ending in 5. This post addresses that gap.

In that post I had stated that after trying briefly to discern a pattern for divisors ending with 5, I'd given up when no obvious pattern suggested itself. Well. This morning I gave it some more thought, and was thrilled to f ind a simple, consistent - and in the end almost tautological - pattern for
divisors ending with 5.

The divisibility rule for 5 itself is almost trivial - it divides any number ending with either 5 or 0. The only problem is, this doesn't tell us anything about checking for divisibility by 15, 25, 35, 45, etc.

To consider the problem I first set down the odd multiples of 15, 25, 35, etc., getting:

15: 15, 45, 75, 105, 135,...
25: 25, 75, 125, 175, 225,...
35: 35, 105, 175, 245, 315,...

If we omit the 5 at the end of each number a pattern begins to emerge.

15: 1, 4, 7, 10, 13,...
25: 2, 7, 12, 17, 22,...
35: 3, 10, 17, 24, 31,...

True, it's an arithmetic progression just as was the previous set of series  (hardly a surprise in a multiplication table). But the second batch of number sequences with smaller items is easier to
 comprehend and mine for a pattern.

For a start we see that for 15 the difference between the terms is 3, for 25, 5 and for 35, 7.

Thus, the difference between successive terms in each case is our divisor (recall that we are only dealing with divisors ending in 5) divided by 5.

We are now ready to formulate the rules, but first some definitions.

We shall use the vertical bar, |, to signify divisibility. That is, a|b means a is divisible by b.

Let's call the divisor (10x +5) . Therefore the divisor can also be considered as 5*n (thus, n is 3 for divisor 15, 5 for divisor 25, 7 for divisor 35, etc.).

The dividend in this case is of the form (10r+u), where u can only be 5 or 0.

The formula is simple.
For u=5,
(10r+u) | (10x + 5 )  if (r-x) | n

If u=0,
(10r+u) |  (10x+5) if r|n.


Let's look at some examples, one for u=5 and one for u=0.

Is  7645  |  55?
Here, r=764, u=5, x=5, n=11.
Since u=5, is (r-x) | n?
Is (764-5) | 11?
759 | 11, so 7645 |  55.
Divisible!

Is 15290 |   695?
Here, r=1529, u=0, x =69, n=139.
Since u=0, is 1529 |  139?
It is. So 15290 |  695.
Divisible!

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 .

Divisibility - A more general approach
Niranjan Ramakrishnan
May 8, 2018

Everyone is taught some basic rules for checking if a number is divisible by 2, 3, 4, 5, etc . Any even number is divisible by 2. For 3, if the sum of its digits is divisible by 3, so is the number itself. If the number formed by its last two digits can be divided clean by 4, the number is divisible by 4. Any number ending in either a zero or a 5 is divisible by 5. Any An even number divisible by 3 is divisible by 6. The rule for 8 is similar to that for 4, except that the number tested is that formed by the last three digits - not the last two. The rule for 9 is identical to that for 3 - if the sum of the digits is divisible by 9, so is the number. The test for 10 is trivial - any number ending in a 0. One other rule is taught: if total of the odd positioned and even-positioned digits is either equal or differs by a multiple of 11, the number is divisible by 11.

If still awake a reader might notice that the rules summary is missing any mention of 7. This is because in teaching rules of divisibility the number 7 stood in some bad odor, unamenable to  ready rulemaking. We used to declare, as our elders nodded mournfully, that there was no rule for 7.

But there does exist a divisibility rule for 7, as I learned from the Internet some years ago. Yesterday I stumbled on the fact that the rule for 7 contains an approach that blows open a path to check divisibility more general than the techniques we were taught.

Let's start with the divisibility formula for 7. First some definitions. Three concepts are involved. The number being tested is broken into two parts - the last digit, the number in the units or 1's place, which we shall call 'u', and the rest of the original number, which we shall call, 'r'. That's two of the three concepts.

E.g., if our number is 266, u=6 and r=26.
The algorithm for7 is as follows: if r-2*u is divisible by 7, then so is the original number.
Applying this to 266, r-2*u = 26-2*6 = 26-12 = 14
Since 14 is divisible by 7, so is 266 (7 times 38).
Note that a subtraction result of 0 also means the number is divisible, as zero is divisible by 7 (or by any Natural number).
E.g., 84. r=8, u=4. r-2*u gives 0.

The third concept is the multiplier 'm', 2 in this algorithm for 7. How exactly 'm' is to be calculated will be discussed shortly.
 
I rested content in this knowledge until yesterday, when a sudden email arrived from my sister, comprising a single line, "What is the formula for divisibility by 17?"

I didn't know, of course. Wondering if there wasn't something for 17 along the lines of the formula for 7, I  began to explore in my mind various combinations and to my surprise chanced upon one which seemed to work. All that was required was to use 5 as the multiplier in place of 2. Thus for 17 itself, r=1, u=7,m=5, and r-m*u = -34. For 102, 10-5*2= 0!

This success emboldened me look at 27, and I found that a multiplier of 8 worked beautifully. It seemed to be a series - 2(7), 5(17) 8(27), 11(37), 14(47), etc. in short, m=3x+2, where x is 0 for 7, 1 for 17, 2 for 27, 3 for 37,...25 for 257, etc.

Next I tackled 13, the next prime number without a divisibility formula (that I knew of). Turned out to have one, but of the form r + m * u, i.e., a plus instead of a minus. For 13, m=4. For 23 m= 7, etc. the general expression being m=3x+1, where x is 0 for 3, 1 for 13, 2 for 23, ...25 for 253, etc.

Then for numbers ending in 9, the formula is m=x+1, where x is again 0 for 9, 1 for 19,... 25 for 259, etc.  We have to check r+m*u,  just like for numbers ending in 3.

Finally,  numbers that end in 1. Here, m=x,  where x is 0 for 1, 1 for 11, 2 for 21, 3 for 31,... 25 for 251, etc.  The number to test is r-m*u.

Deciding to press my luck I ventured into numbers ending in 5. No obvious pattern suggested itself.

But there is an alternating pattern to the four number-endings,.  1 (r-m*u),  3 (r+m*u),  7 (r-m*u)  and 9 (r+m*u).

I'm sure students of mathematics are familiar with these formulas,  but I certainly hadn't encountered rules for 7, 13, 19, etc.  during my several years of science and mathematics in school and college,  which is why the utter simplicity - and generality -  brought so much delight when I uncovered them.

One example each of divisors ending in 1, 3, 7 and 9.

Is 372 divisible by 31?
Formula: r-m*u and m=x.
Here,  r=37, u=2, m(=x)=3.
r-m*u = 37-2*3 = 37-6  = 31. Divisible!

Is 559 divisible by 43?
Formula: r+m*u,  where m=3x+1.
Here,  r=55,  u=9, m(3x+1)=13.
r+m*u = 55+13*9 = 55+117 = 172. 172 = 4 * 43. Divisible!

Is 1164 divisible by 97?
Formula: r-m*u,  where m=3x+2.
Here,  r=116, u=4,m(3x+2)=29.
r-m*u = 116-29*4 = 116-116 = 0. Divisible!

 Is 1157 divisible by 89?
Formula: r+m*u,  where m=x+1.
Here, r=115, u=7, m(x+1)=9.
r+m*u = 115+9*7 = 115+63 = 178. 178 is 2 times 89. Divisible!