You've shown that if you start with a multiple of 7, you can construct 10 other numbers (1 for each y in 0..9) that are also divisible by 7 and which obey cLive's rule. It's not the same as showing that every number obeys cLive's rule.

Using the "|" to mean divides (so 7| x + y means "7 divides x + y") and <=> to mean "if and only if". 

(1)7 | x - 2y   <=>  7 | 10x - 20y
(2)7 | 10x - 20y  <=>  7 | 10x + y

so 

7 | x - 2y  <=>  7 | 10x + y

[download]

(1) is true because 10 has no factor in common with 7 so multiplying by 10 does not effect divisbility

(2) is true because 21y is divisible by 7 so adding 21y will have no effect on divisibility

This holds for any x and y and every number can be written as 10x+y for some suitable x and y.

The key to finding a rule for divisibility mod N is finding the inverse of 10 mod N. That is, finding I such that 

(10 * I) % N == 1

[download]
So for example if N is seven the inverse of 10 is 5: 5 * 10 = 50 = 7*7 + 1. So, thinking only in terms of remainder on division by 7, 
10x + y = 5 * (10x + y) = 50x + 5y = x + 5y = x - 2y

[download]
and mod 21, 10 * 19 = 190 = (9*21) +1. So thinking mod 21 we have 
10x + y = 19*(10x+y) = 190x +19y = x + 19x = x - 2y

[download]
so 10x + y is divisible by 21 whenever x - 2y is too.

This methods works for non-primes, what's important is that the number doesn't share any factors with 10. ie. it's not divisible by 2 or 5.

Update: fixed a typo I had (N * I) % N = 1 in the definition of inverse. Also fixed a missing / that messed the formatting.

In reply to Re: (OT) Division-by-seven, division-by-n by fergal
in thread (OT) Division-by-seven, division-by-n by japhy

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.