20040916, 09:09  #1 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}·3^{3}·19 Posts 
Divisiblity by 7
Recently I came across a problem which required 'considerable' theoretical depth in solving it and I thought that its worthwhile to present here. How would you explain the fact that if any set of integers is repeated six times to form another integer it must be divisible by seven? Examples: 111111 , 121212121212, 143143143143143143 etc : Mally 
20040916, 09:34  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
We have a*x^5+...+a, i.e. a=1 x=10, a=12 a=100, a=143 x=1000 in your examples.
If x != 1 (mod 7), the subgroups of (Z/Z7)* generated by x includes 1 and thus the negative for each element. SInce the order of the subgroup divides 6, going through x^5+...x^0 includes all elements in integral number of times, they therefore sum to 0 (mod 7). I haven't checked, but if I'm right the trick should fail in octal numbers, because all x^k are == 1 (mod 7). Alex 
20040916, 10:59  #3 
Aug 2002
Termonfeckin, IE
101011000011_{2} Posts 
OK! It's been a damn long time since I studied groups and have forgotten most of it. Anyone care to remind me?

20040916, 11:39  #4 
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
Oops, I'm wrong! The subgroups generated by 2 and 4 do not include 1, as the order of 2 and 4 is 3. This subgroup does, however, consist of {1,2,4}, which again sums to zero (mod 7).
a*x^5+...+a = a*(x^5+...+x^0). If a == 0 (mod 7), the result is trivially divisible by 7. Otherwise, the results is divisible by 7 iff x^5+...+x^0 is. ((Z/Zp)* is free of zero divisors, so a*b == 0 <=> a==0 or b==0). If the order of x (mod 7) is even, the subgroup generated by x includes x^(ord(x)/2) == 1. As we are going through the different x^k, k=0, ..., 5, we generate x^0 == 1, x^1 = x, ..., x^(ord(x)/21), x^(ord(x)/2) == 1, x^(ord(x)/2+1) == x, ..., x^(ord(x)1) == x^(ord(x)/21) Each element so generated can be paired up with it's negative, so they sum to zero. If the order of x (mod 7) is odd, the case ord(x)=3 just happens to generate elements which again sum to a multiple of 7. The case ord(x)=1, i.e. x=7*k+1, does not generate multiples of 7 if a != 0 (mod 7): x^k == 1 for all k, so x^0 + ... + x^5 == 6 (mod 7), and the results will be 6*a (mod 7). I.e. 10^6 == 1 (mod 7), and x=10^6 a=1 yields 1000001000001000001000001000001 = 3 * 19 * 101 * 9901 * 52579 * 333667 * 999999000001 No factor 7 here. Alex 
20040916, 14:34  #5 
Mar 2004
3·127 Posts 
True.
If the string is 6 digits long and not divisible by 7, the whole thing is not. 123456123456123456123456123456123456 / 7 
20040917, 04:02  #6 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}×3^{3}×19 Posts 
Divisibility by 7
HINT:
A rigorous but elegant proof will depend on the use of a G.P., Fermats (little) theorem and a theorem on polynomials. Mally 
20040917, 06:43  #7 
Mar 2004
3·127 Posts 
it can be proven for the length of the substring of 1..5 but not 6.
111112 111112 111112 111112 111112 111112 is not divisible by 7; it has a remainder of 6. proof from 1 to 5 digits [mod 6] << 10^n mod 6, 10^n1 mod 6, ..... 10^3 mod 6, 10^2 mod 6, 10^1 mod 6, 10^0 mod 6 <1 digit> .....2 3 1 2 3 1 ..... a a a a a a so a: 2 3 1 +2 +3 +1 = 0 <2 digits> .....2 3 1 2 3 1 2 3 1 2 3 1 ..... a b a b a b a b a b a b so a: 2 1 +3 2 1 +3 = 0 b: 3 +2 +1 3 +2 +1 = 0 <3 digits> .....2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 ..... a b c a b c a b c a b c a b c a b c so a: 2 +2 2 +2 2 +2 = 0 b: 3 +3 3 +3 3 +3 = 0 c: 1 +1 1 +1 1 +1 = 0 4 digits similar to 2 digits 5 digits similar to 1 digit. QED. 
20040918, 17:07  #8  
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}×3^{3}×19 Posts 
Divisibility by 7
Quote:
Thank you akruppa and Garo for your comments on my thread. I dont think group theory is required to solve this problem. biwema: I must admit your statement was unexpected and startling by providing a counterexample of 111112. I had to put on my thinking cap ro prove how wrong it was. Thats why I took so long to reply. The fact is that my theory is based on sound unerring theorems viz: G.P., Fermats (little) theorem and a theorem on polynomials which are basic. I knew at once that your division was wrong and not my theory. But in all fairness it troubled me to give the benefit of the doubt to you Moreover the divisibility by seven is not based on the number of digits in the set or the order. It is completely independent. It is true for sets of any NO. OR ORDER PROVIDED ONLY 6 of the same sets are used. I would advise you to carefully recheck your division as it is completely erroneous. If correct you will find that 7 goes in exactly with no remainder at all. On the positive side your error in division and the refuting of it has strenghtened my faith in the power and beauty of mathematics. In a later post I will give my elegant theory in more detail and you will marvel at the simplicity but power of deduction. Mally 

20040918, 18:06  #9  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
Code:
? 111112111112111112111112111112111112%7 %1 = 6 ? Alex 

20040918, 22:52  #10 
May 2003
3013_{8} Posts 
The true result should be as follows:
In base 10, to check that a number is divisible by 3, or by 9, one just adds up all the digits, and if this is a number that has more than one digit, we repeat this process, until we get down to a onedigit number. And then we just have to check that it is divisible by 3 or 9. In base 10, to check that a number is divisible by 7, we have to break up integers into 6 digit blocks, and do this same process. For example, to check whether 1103949129439534 is divisible by 7 we take the last six digits 439534, the next six digits 949129, the next six digits 1103, and add all these together to get 1389766. Then, for this new number we again take the last six digits 389766, and the next six digits 1, and add them together to get 389767. Then we check whether this new number is divisible by 7 (which it is). So the original number must be divisible by 7 (which it is). There is a slight simplification one can make. It is similar to how we check whether a number is divisible by 11. The rule for 11 is to add and subtract every other digit from one another. So, to check that 103494 is divisible by 11 or not, we do 49+43+01=5, which is not divisible by 11. For 7, we have to take 3 digits at a time. So, using 1103949129439534 again, we look at 534439+129949+1031=623 (which is divisible by 7). The same test will work for 13. (This works because 10^{3} is congruent to 1 modulo 7 and 1 modulo 13). Best, ZetaFlux Last fiddled with by ZetaFlux on 20040918 at 22:54 
20040920, 12:02  #11  
Nov 2003
16444_{8} Posts 
Quote:
Everyone seems to be making very heavy going out of something that is quite simple. Observe that 7*11*13 = 1001 1001 * XYZ = XYZXYZ Enough said? 
