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

Niranjan RamakrishnanMay 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 .