Divisiblity by 7

mfgoode · 2004-09-16, 09:09

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

akruppa · 2004-09-16, 09:34

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

garo · 2004-09-16, 10:59

OK! It's been a damn long time since I studied groups and have forgotten most of it. Anyone care to remind me?

akruppa · 2004-09-16, 11:39

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)/2-1), x^(ord(x)/2) == -1, x^(ord(x)/2+1) == -x, ..., x^(ord(x)-1) == -x^(ord(x)/2-1)
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

biwema · 2004-09-16, 14:34

True.

If the string is 6 digits long and not divisible by 7, the whole thing is not.

123456123456123456123456123456123456 / 7

mfgoode · 2004-09-17, 04:02

HINT:

A rigorous but elegant proof will depend on the use of a G.P., Fermats (little)
theorem and a theorem on polynomials.

Mally

biwema · 2004-09-17, 06:43

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^n-1 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.

mfgoode · 2004-09-18, 17:07

Quote:

Originally Posted by biwema

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]
<<
[color=#F5F5FF]
10^n mod 6, 10^n-1 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.

:

:

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 counter-example 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 re-check 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

akruppa · 2004-09-18, 18:06

Quote:

Originally Posted by mfgoode

I would advise you to carefully re-check your division as it is completely erroneous.
If correct you will find that 7 goes in exactly with no remainder at all.

Looks completely correct to me:

Code:

? 111112111112111112111112111112111112%7
%1 = 6
?

Also fits my theory: 111112 == 1 (mod 7) and 10^6 == 1 (mod 7) so the result is 6 (mod 7).

Alex

Zeta-Flux · 2004-09-18, 22:52

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 one-digit 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 4-9+4-3+0-1=-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 534-439+129-949+103-1=-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,
Zeta-Flux

R.D. Silverman · 2004-09-20, 12:02

Quote:

Originally Posted by Zeta-Flux

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 one-digit 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 4-9+4-3+0-1=-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 534-439+129-949+103-1=-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,
Zeta-Flux

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?

2004-09-16, 09:09	#1
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²×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

2004-09-17, 04:02	#6
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²×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

2004-09-18, 22:52	#10
Zeta-Flux May 2003 60B₁₆ 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 one-digit 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 4-9+4-3+0-1=-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 534-439+129-949+103-1=-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, Zeta-Flux Last fiddled with by Zeta-Flux on 2004-09-18 at 22:54

2004-09-16, 09:34	#2
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	We have ax^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

2004-09-16, 10:59	#3
garo Aug 2002 Termonfeckin, IE 2764₁₀ Posts	OK! It's been a damn long time since I studied groups and have forgotten most of it. Anyone care to remind me?

2004-09-16, 11:39	#4
akruppa "Nancy" Aug 2002 Alexandria 2,467 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). ax^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 ab == 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)/2-1), x^(ord(x)/2) == -1, x^(ord(x)/2+1) == -x, ..., x^(ord(x)-1) == -x^(ord(x)/2-1) 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=7k+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 6a (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

2004-09-16, 14:34	#5
biwema Mar 2004 101111101₂ Posts	True. If the string is 6 digits long and not divisible by 7, the whole thing is not. 123456123456123456123456123456123456 / 7

2004-09-17, 06:43	#7
biwema 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^n-1 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.