mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-09-16, 09:09   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Default 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
mfgoode is offline   Reply With Quote
Old 2004-09-16, 09:34   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-09-16, 10:59   #3
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

1010110000112 Posts
Default

OK! It's been a damn long time since I studied groups and have forgotten most of it. Anyone care to remind me?
garo is offline   Reply With Quote
Old 2004-09-16, 11:39   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-09-16, 14:34   #5
biwema
 
biwema's Avatar
 
Mar 2004

3·127 Posts
Default

True.

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

123456123456123456123456123456123456 / 7
biwema is offline   Reply With Quote
Old 2004-09-17, 04:02   #6
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Thumbs up 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
mfgoode is offline   Reply With Quote
Old 2004-09-17, 06:43   #7
biwema
 
biwema's Avatar
 
Mar 2004

3·127 Posts
Default

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.
biwema is offline   Reply With Quote
Old 2004-09-18, 17:07   #8
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Thumbs up Divisibility by 7

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
mfgoode is offline   Reply With Quote
Old 2004-09-18, 18:06   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-09-18, 22:52   #10
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

30138 Posts
Default

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
Zeta-Flux is offline   Reply With Quote
Old 2004-09-20, 12:02   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Thumbs up

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?
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 12:47.

Wed Dec 2 12:47:56 UTC 2020 up 83 days, 9:58, 3 users, load averages: 4.63, 4.66, 4.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.