number theory: ah, those funny li'l modulos

There were only a handful of tricks with numbers that the typical elementary school student would be inculcated with during those years I enjoyed (well, attempted to enjoy) primary education. To cast the bleak bleaker, the divisibility test by 3 is often the only ubiquitously taught trick possessing some semblance of novelty. In case anyone wondered as a kid but failed to discover the reason, modulus arithmetic is the preferred foundation with which one derives efficient divisibility tests. For some reason still unbeknownst to me, I decided to raise this ol' topic and began concocting digit-wise divisibility tests for the primes 7 and 11. I urge readers to please have ready several pitchers of water, since what follows is fairly dry...

When X is a string (of some radix) of numerical value Σ(X[k]*radix^k)_{∀k∈0..X.length-1⊆Z}, then (int)X ≡ 0 mod Y iff: Σ(X[k] * cycle[k])_{∀k∈0..X.length⊆Z} ≡ 0 mod Y, where cycle is the repeating series { radix^k mod Y }.

Let's pick a radix we all know and love, base10:
Let Dn = { 10⁰, 10¹, 10², ... }
Dn mod 3 = { 1, 1, 1, ... } = Cycle (1). Since cycle[k] = 1, we get the age-old mantra "X is divisible by 3 iff the sum of digits is divisible by 3".

But let's look beyond 3,
Dn mod 7 = cycle ( 1, 3, 3*3≡9≡2, 2*3≡6≡-1 ..) = cycle (1, 3, 2, -1, -3, -2)
Dn mod 11 = cycle (1, 10≡-1 ..) = cycle (1,-1)

Interestingly, but with less power than an iff relationship, since lcm(2,6) = 6 and both Dn mod 7 and Dn mod 11 have half-cycles (-1 as an element), then X ≡ 0 mod 77 if X in decimal form can be grouped into 3digit strings, where every other 3digit string is marked red and those in between are marked blue, and the { reds } minus { blues } = Null.

For exampe, let red = { 123, 444, 812, 912, 083, 948, 020, 436 }
Thus, blue = { 123, 444, 812, 912, 083, 948, 020, 436 }
Let shuffle(blue) = { 444, 948, 912, 436, 083, 812, 123, 020 }
Then interlace(red, shuffle(blue)) = 123444 444948 812912 912436 083083 948812 020123 436020. This now yields a base10 string which is divisible by 77 (and obviously also by 2, 5, 7, 11 and all the other factors of their multiple 770): 123444444948812912912436083083948812020123436020

Too big a number to verify with a pocket-calculator? Here's an easy multiple of 77 to generate: 001001 = 1,001. A pocket calculator can verify it is 13*77.

But then, what's the ratio of densities between these simple multiples and the full set of multiples? In the case of 77, cardinality of the full set of multiples for base10 string X is (1/77) * (10^X.length). Cardinality for the parlor-trick partial set is:
Let red_i = ∪(X[6*i+0..6*i+2])
Let blue_i = ∪(X[6*i+3..6*i+5])
Let g = X.length/6
(Π(φ(∃unique j s.t. blue_i = red_j))_{∀i∈0..g-1⊆Z}) * (10^X.length)
= (Π(1 - ((10³-1)/10³)^k)_{∀k∈1..g⊆Z}) * (10^X.length)
= (Π(1 - 0.999^k)_{∀k∈1..g⊆Z}) * (10^X.length)
lim_{X.length→∞}( Π(1 - 0.999^k)_{∀k∈1..g⊆Z} ) ≈ 7.4210E-713
Thus, the ratio of the two is (1/77) : 7.4210E-713 ⇒ 1 : 5.7142E-711. In other words, the parlor trick while being a very good way to generate multiples is a rather improbable way to test for divisibility by 77. The only rigorous divisibility test is the one where iff is ensured instead of the comparatively impotent if.