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!