# Proof of the divisibility rule of 17.

Rule: Subtract 5 times the last digit from the rest of the number, if the result is divisible by 17 then the number is also divisible by 17.

How does this rule work? Please give the proof.

-
Is this homework? The imperative at the end sounds like it. –  celtschk Jul 23 '12 at 10:36
@celtschk: I don't think so, the question probably comes from math.stackexchange.com/questions/174114/… –  Generic Human Jul 23 '12 at 10:44
@celtschk no this is not a homework.This question comes from math.stackexchange.com/questions/174114/… (same link as provided by @generichuman). –  abhinav8 Jul 23 '12 at 10:52
@celtschk if he wanted to mask it as non homework, i'm sure he is clever enough. why would it matter? –  IIIIIllllllllIlllllIIIIIIIIlll Jul 23 '12 at 17:31
@АртёмЦарионов: On one hand, it would matter because it should then get the [homework] tag, on the other hand it would mean that the tone of the last sentence shouldn't bother you because it was just copied from a context where it was appropriate. –  celtschk Jul 23 '12 at 17:41

Write your number $10a+b$.

Then because 10 and 17 are relatively prime, $$17\mid a-5b \iff 17\mid 10a-50b \iff 17\mid 10a+b$$ The last equivalence is because $10a+b-(10a-50b) = 51b$ is always a multiple of 17.

-

Let $$n=\sum_{k=0}^N 10^k a_k$$ be the number we want to test for divisibility, where the $a_k$s are the digits in the decimal expansion of $n$. We form the second number $m$ by the process you describe, $$m = \sum_{k=1}^N 10^{k-1} a_k - 5 a_0 = \frac{n-a_0}{10}- 5 a_0$$ Now suppose $17|m$. Then there exists a natural number $b$ such that $17b = m$. We then have $$17 b = \frac{n-a_0}{10}- 5 a_0$$ $$10 * 17 b = n-a_0- 50 a_0 \implies n= 17(10b + 3a_0)$$ and so $n$ is divisible by 17.

-

10x+y will be divisible by an odd prime p iff a.p.x ~ b(10x+y) is divisible by p.

Now by Euclid's GCD algorithm, we can find integers a,b such that a.p ~ b.10=1 where (p,10)=1.

If p=17, by observation 3.17 - 5.10=1.

So, 3.17.x-5(10x+y)=x-5y.

If this is divisible by 17, so will be 10x+y.

-

$17 = 2^3 + 3^2$

the sum of the exponents of $2$ and $3$ is $(3 + 2)$

i.e. the sum of the exponents is $5$

Now a number can be expressed as $abcde$

i.e. $abcde = (10^4)a + (10^3)b + (10^2)c + (10^1)d + e$

remove the units digit from $abcde$ to get $$abcd = (10^3)a + (10^2)b + (10^1)c + d$$

Now, let $A = abcd - (3 + 2)(e)$

Assume $A$ is divisible by $17$

i.e. $A = abcd - (5)e = (17)k$

i.e. $abcde = (10)(abcd) + e$

i.e. $abcde = (10)((17)k + (5)e) + e$

i.e. $abcde = (170)k + (50)e + e$

i.e. $abcde = (17)(10)k + (51)e$

i.e. $abcde = (17)(10)k + (17)(3)e$

i.e. $abcde = (17)((10)k + (3)e)$

i.e. $abcde$ is indeed divisible by $17$

-
How are you using $\, 17 = 2^3+3^2\,$ to compute $\: 10^{-1}\equiv -5\pmod{17}$ ? $\ \$ –  Bill Dubuque Jul 23 '12 at 13:56
rajesh do you have an answer for the above question? –  IIIIIllllllllIlllllIIIIIIIIlll Jul 23 '12 at 17:29
The modulus of a congruence a=b (mod m) is the number m. It is the "base" with respect to which a congruence is computed (i.e., m gives the number of multiples of a that are "thrown out"). For example, when computing the time of day using a 12-hour clock obtained by adding four hours to 9:00, the answer, 1:00, is obtained by taking 9+4=1 (mod 12) (i.e., adding the hours with modulus 12). –  Rajesh K Singh Jul 27 '12 at 5:58
please clarify what is $10^{-1}$ –  Rajesh K Singh Jul 29 '12 at 10:38
is it $\frac{1}{10}$ –  Rajesh K Singh Jul 29 '12 at 10:39

Write the original number as 10x+y to separate out the last digit (y) from the number without the last digit (x). Recognize that divisibility by a 17 means you can write the number as 17n for a positive integer n. So our statement is if x-5y=17n then 10x + y = 17m, where x,y,m,n are positive integers.

Assume x - 5y = 17n. Now we try to get the left-hand side to look like our original number. First multiply both sides by 10. (10x - 50y = 170n), and then add 51y to both sides. (10x+ y = 170n + 51y). Factor 17 from the right hand side. (10x+y=17(10n+3y)). Recognize that 10n+3y is a positive integer as n and y are integers, let's define it as m, proving that 10x+y=17m meaning that the original number is divisible by 17 if x-5y was divisible by 17.

-