Source: An original extension of UofCF's Problem of the Week ending 11/9/97.
If the original number is N, the basic method for divisiblility by a string of k 1s is to break the N into strings of length k, starting from the units digit (extending zeros to the left as needed). Sum all these numbers together, letting any carry be added into the units digits. If the result consists of all the same digits, the original number N is evenly divisible by k 1s.
My own proof (others are below): Adding the lowest k digits to the rest of N (> 10^k) is equivalent to adding 999...9*(k-digits) to N (where there are k 9s). The added number is divisible by k 1s (since it's multiplied by k 9s.) Dividing by 10^k doesn't change the divisibility by k 1s (there are no common prime factors), and the new number N' can be checked as before. This process can thus be repeated until there are only k digits left.
>From Philippe Fondanaiche Question 1 Any integer N can be written as follows: N = 10^3nxa(n) + 10^3(n-1)xa(n-1) + ............+ 1000a(1) + a(0) where 0<= a(i) <=999 whatever i = 0,1,2,.......n N is divisible by 111 if and only if S = sum[a(i)] for i=1 to n,is divisible by 111. Indeed 10^3n - 1 is divisible by 111 whatever n. So N - S is divisible by 111 whatever the terms a(i). If N is divisible by 111,S = N - (N-S) is also divisible by 111. Reciprocally, if S is divisible by 111, it is also the case for N = S + (N-S). Consequently, we calculate S = sum[a(i)]. If S > 1000, we have the terms a'(i) and we calculate sum[a'(i)] and so on...If the final result is 111 or 222 or......999, we can infer that N is divisible by 111. Question 2 Any integer N can be written as follows: N = 10^kn x a(n) + 10^k(n-1) x a(n-1) + .......... + 10^k x a(1) + a(0). where 0<= a(n) <= 10^k - 1 With the way of reasoning described in the question 1,N is divisible by A = 1111...111 (k times) if and only if S = sum[a(i)] is divisible by A. If S >= 10^(k+1), the operation is repeated in order to obtain S<= 10^k - 1. If S=1111...111 or 2222...222 or 9999...999, N is divisible by A.
From Jeff Soesbe:
I'll give the solution for part 2, and part 1 is a specific case.
Let X be a n-digit number whose digits are
a_(n-1) a_(n-2) a_(n-3) ... a_1 a_0, ie
X = [a_(n-1) * 10^(n-1)] + [a_(n-2) * 10^(n-1)] + ... +[a_1 * 10] + [a_0]
Let Y be a number consisting of r 1's, ie
Y = 10^(r-1) + 10^(r-2) + ... + 10^2 + 10^1 + 1
Form sums from the digits of X as follows:
Sum_0 = a_0 + a_r + a_2r + ... + a_kr + ...
Sum_1 = a_1 + a_(r+1) + a_(2r+1) + ... + a_(kr+1) + ...
Sum_2 = a_2 + a_(r+2) + a_(2r+2) + ... + a_(kr+2) + ...
...
Sum_(r-1) = a_(r-1) + a_(2r-1) + a_(3r-1) + ... + a_(kr+r-1) + ...
Condition: If all the Sum_i are equal, then X is divisible by Y.
==========
Why:
(NOTE: I think it should be okay, I've proofread it a couple times.
Let me know if anything seems squirrely...)
We can think of X as being composed of a sequence of t r-digit numbers,
where tr > n >= (t-1)r.
So, the digits of X are X_(t-1) ... X_3 X_2 X_1 X_0
where the digits of X_i are a_(ir+r-1) ... a_(ir+2) a_(ir+1) a_ir
and X_(t-1) might or might not have r digits, depending on the value of n.
This means that
X = [X_(t-1) * 10^r(t-1)]
+ [X_(t-2) * 10^r(t-2)]
+ ...
+ [X_1 * 10^r]
+ X_0
We can regroup this total as:
X = [X_(t-1) * (10^r(t-1) - 1)]
+ [X_(t-2) * (10^r(t-2) - 1)]
+ ...
+ [X_1 * (10^r - 1)]
+ [X_(t-1) + ... + X_1 + X_0]
Now, we simplify the first (t-1) terms of this sum
= [X_(t-1) * (10^r(t-1) - 1^(t-1))]
+ [X_(t-2) * (10^r(t-2) - 1^(t-2))]
+ ...
+ [X_1 * (10^r - 1)]
+ [X_(t-1) + ... + X_1 + X_0]
= [X_(t-1) * (10^r - 1) * {10^r(t-2) + 10^r(t-3) + ... + 10^r + 1}]
+ [X_(t-2) * (10^r - 1) * {10^r(t-3) + 10^r(t-4) + ... + 10^r + 1}]
+ ...
+ [X_1 * (10^r - 1)]
+ [X_(t-1) + ... + X_1 + X_0]
= (10^r - 1) *
([X_(t-1) * {10^r(t-2) + 10^r(t-3) + ... + 10^r + 1}]
+ [X_(t-2) * {10^r(t-3) + 10^r(t-4) + ... + 10^r + 1}]
+ ...
+ [X_1])
+ [X_(t-1) + ... + X_1 + X_0]
Now, we note that
(10^r - 1) = (10 - 1) * (10^(r-1) + 10^(r-2) + ... + 10^1 + 1)
The second term is the given number Y, so
(10^r - 1) = 9 * Y
and the first part of X is divisible by Y.
To determine the value of [X_t + X_(t-1) + ... + X_1 + X_0], we can
just look at the sum in terms of its digits
[X_(t-1) + ... + X_1 + X_0]
= a_n a_(n-1) ... a(t-1)r
+ a_((t-2)r + r-1) ... a_(t-2)r
+ ...
+ a_(r-1) ... a_1 a_0
Arranging the sum by powers of 10, we get
[X_(t-1) + ... + X_1 + X_0]
= 10^(r-1) * [... + a_(kr+r-1) + ... + a_(r-1)]
+ 10^(r-2) * [... + a_(kr+(r-2)) + ... + a_(r-2)]
+ ....
+ 10^1 * [... + a_(kr+1) + ... + a_1]
+ 1 * [... + a_kr + ... + a_0]
The terms in the [brackets] are just the digit sums (Sum_i) of the
number X. By the above condition, they are all equal. Let
them equal Z. We have:
[X_(t-1) + ... + X_1 + X_0]
= 10^(r-1) * Z
+ 10^(r-2) * Z
+ ...
+ 10^1 * Z
+ 1 * Z
= Z * (10^(r-1) + 10^(r-2) + ... + 10^1 + 1)
The second term is the the given number Y, so
[X_(t-1) + ... + X_1 + X_0] = Z * Y
and the second part of X is divisible by Y.
Putting it all together, we get:
X = Y * {
9 * ([X_(t-1) * {10^r(t-2) + 10^r(t-3) + ... + 10^r + 1}]
+ [X_(t-2) * {10^r(t-3) + 10^r(t-4) + ... + 10^r + 1}
+ ...
+ [X_1])
+ Z
}
Where the X_i are the r-digit numbers of X as given above and
Z is the digit sum of X as given above.
So, under the stated condition, X is divisible by Y, giving us
our desired divisibility test:
1) Separate X into r-digit numbers, starting from the ones' place,
where r is the number of ones in Y. It's fine if the last (left-most)
number doesn't have r digits.
2) Stack the numbers vertically and add the digits in each
column. If the sums of the digits in each column are equal, the
number X is divisible by Y.
And, part one is the specific case where r=3 and Y=111.
(gaagh. Where's that Sigma key for summations when you need it...)