# Seven divides

Arjun Shastry

Ranch Hand

Posts: 1893

posted 11 years ago

- 0

This problem is really killing me.See if you can solve.

Number formed by any set of integers repeating 6 times is always divisible by 7

Eg 1)111111 is divisible by 7

Eg 2)898989898989 is divisible by 7

Eg 3)307307307307307307 is divisible by 7

..................................

Eg 6)107451107451107451107451107451107451 is divisible by 7

..... and so on

Why this happens?

Number formed by any set of integers repeating 6 times is always divisible by 7

Eg 1)111111 is divisible by 7

Eg 2)898989898989 is divisible by 7

Eg 3)307307307307307307 is divisible by 7

..................................

Eg 6)107451107451107451107451107451107451 is divisible by 7

..... and so on

Why this happens?

MH

posted 11 years ago

- 0

since 7 will divide 111111, it will divide any multiple of this, giving easy access to 222222, 333333, etc.

7 will also divide 101010101010, giving us all the 2digit numbers repeated 6 times.

same for 100100100100100100 and the 3 digit numbers.

now, is this a proof that it works for EVERY number repeated? no. but if we investigate a little further...

and look at how many times 7 goes into each of those, a pattern starts to develop...

111111/7 = 15873

101010101010/7 = 14430014430

100100100100100100/7 = 14300014300014300

100010001000100010001000 / 7 = 14287143000014287143000

that was as far as i went. not sure if this proves anything or not, or if it's a red herring. But it's interesting, imho

7 will also divide 101010101010, giving us all the 2digit numbers repeated 6 times.

same for 100100100100100100 and the 3 digit numbers.

now, is this a proof that it works for EVERY number repeated? no. but if we investigate a little further...

and look at how many times 7 goes into each of those, a pattern starts to develop...

111111/7 = 15873

101010101010/7 = 14430014430

100100100100100100/7 = 14300014300014300

100010001000100010001000 / 7 = 14287143000014287143000

that was as far as i went. not sure if this proves anything or not, or if it's a red herring. But it's interesting, imho

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Arjun Shastry

Ranch Hand

Posts: 1893

Maulin Vasavada

Ranch Hand

Posts: 1873

posted 11 years ago

- 0

Hi Arjun

I tried to prove it by Math Induction.

The idea is- if we have n-digit number repeating 6 times, that number can be given by,

NUMBER=a * Sigma of (b ^ i) where i=0 to 5

b = 10 ^ n

a = the number that is getting repeated 6 times.

e.g.

1. in 111111 , a = 1, b = 10 ^ 1

2. in 898989898989 , a = 89, b = 10 ^ 2

3. in 307307307307307307 , a = 307, b = 10 ^ 3 and so on...

now, by Math Induction,

Case 1: n =1

------------

NUMBER = a * Sigma (10 ^ i) where i = 0 to 5

=> NUMBER = a * 111111

Which is divisible by 7,

Case 2: Assume for n=k statement is true i.e.

---------------------------------------------

NUMBER = a * Sigma (10 ^ (k*i) ) where i = 0 to 5

is divisible by 7

Case 3: For n=k+1 we have,

--------------------------

NUMBER = a * Sigma (10 ^ ((k+1)*i) ) where i = 0 to 5

=> NUMBER = a * Sigma (10 ^ (k*i + i) )

=> NUMBER = 10* a * Sigma (10 ^ (k*i))

=> NUMBER = 10 * a * NUMBER_FOR_(n=k)

and From case-2 we know NUMBER_FOR_(n=k) is divisible by 7 hence the current NUMBER is also divisible by 7...

Well, this is quite simple approach but I don't know how to validate if Math Induction is really applicable here. I know in some cases we can't apply Math Induction. e.g. To prove that Person having many hair on head is bald

So any mathematician might want to explain this from pure math perspective..

Regards,

Maulin

I tried to prove it by Math Induction.

The idea is- if we have n-digit number repeating 6 times, that number can be given by,

NUMBER=a * Sigma of (b ^ i) where i=0 to 5

b = 10 ^ n

a = the number that is getting repeated 6 times.

e.g.

1. in 111111 , a = 1, b = 10 ^ 1

2. in 898989898989 , a = 89, b = 10 ^ 2

3. in 307307307307307307 , a = 307, b = 10 ^ 3 and so on...

now, by Math Induction,

Case 1: n =1

------------

NUMBER = a * Sigma (10 ^ i) where i = 0 to 5

=> NUMBER = a * 111111

Which is divisible by 7,

Case 2: Assume for n=k statement is true i.e.

---------------------------------------------

NUMBER = a * Sigma (10 ^ (k*i) ) where i = 0 to 5

is divisible by 7

Case 3: For n=k+1 we have,

--------------------------

NUMBER = a * Sigma (10 ^ ((k+1)*i) ) where i = 0 to 5

=> NUMBER = a * Sigma (10 ^ (k*i + i) )

=> NUMBER = 10* a * Sigma (10 ^ (k*i))

=> NUMBER = 10 * a * NUMBER_FOR_(n=k)

and From case-2 we know NUMBER_FOR_(n=k) is divisible by 7 hence the current NUMBER is also divisible by 7...

Well, this is quite simple approach but I don't know how to validate if Math Induction is really applicable here. I know in some cases we can't apply Math Induction. e.g. To prove that Person having many hair on head is bald

So any mathematician might want to explain this from pure math perspective..

Regards,

Maulin

Arjun Shastry

Ranch Hand

Posts: 1893

posted 11 years ago

- 0

I think that should work.My approach was different.

Let N = 444444

Then N = 4*Math.pow(10,5) + 4*Math.pow(10,4) + 4*Math.pow(10,3) + 4*Math.pow(10,2) + 4*Math.pow(10,1) + 4*Math.pow(10,0)

Now write 10 as 7+3

so N = = 4*Math.pow(7+3,5) + 4*Math.pow(7+3,4) + 4*Math.pow(7+3,3) + 4*Math.pow(7+3,2) + 4*Math.pow(7+3,1) + 4*Math.pow(7+3,0)

If we expand using binomial theorem,then 7 will be in all terms except few terms.Those terms will be Math.pow(3,5),Math.pow(3,4)....

so N = (many things in which 7 is a factor)+[4*Math.pow(3,5)+4*Math.pow(3,4) +4*Math.pow(3,3) +4*Math.pow(3,2) +4*Math.pow(3,1) +4*Math.pow(3,0)]

Let E be the expression in square bracket.

E = 4*(Math.pow(3,5)+Math.pow(3,4)+Math.pow(3,3)+Math.pow(3,2)+Math.pow(3,1)+Math.pow(3,0))

As you can see,its a geometric progression.

1+3+Math.pow(3,2)+Math.pow(3,3)+...........

Sn in above case for 6 terms will be,

Sn = 1*(Math.pow(3,6)-1)/(3-1)

When three digits will be repeated 6 times,

Sn = 1*Math.pow(3,18)-1)/(3-1)

In short,

Sn = 1*Math.pow(3,6m)-1)/2----------(1)where m>=1

now,to prove Math.pow(3,6m)-1 is divisible by 7, we can use induction.

For m = 1,its Math.pow(3,6)-1 which is divisible by 7-----(2)

Let it be true for m = k

so Tk = Math.pow(3,6k)-1 is divisible by 7------(3)

Now Tk+1 = Math.pow(3,6(k+1))-1

= Math.pow(3,6k+6)-1

= (Math.pow(3,6k))*Math.pow(3,6) - 1

= (Math.pow(3,6k))*Math.pow(3,6) - 1 +Math.pow(3,6)-Math.pow(3,6)

= Math.pow(3,6){Math.pow(3,6k)-1} + Math.pow(3,6)-1

By (3),left term is divisible by 7 and Math.pow(3,6)-1 is divisble by 7

Hence Tk+1 is divisible by 7

Hence expression E is divisible by 7

Hence number N is diisible by 7.

Let N = 444444

Then N = 4*Math.pow(10,5) + 4*Math.pow(10,4) + 4*Math.pow(10,3) + 4*Math.pow(10,2) + 4*Math.pow(10,1) + 4*Math.pow(10,0)

Now write 10 as 7+3

so N = = 4*Math.pow(7+3,5) + 4*Math.pow(7+3,4) + 4*Math.pow(7+3,3) + 4*Math.pow(7+3,2) + 4*Math.pow(7+3,1) + 4*Math.pow(7+3,0)

If we expand using binomial theorem,then 7 will be in all terms except few terms.Those terms will be Math.pow(3,5),Math.pow(3,4)....

so N = (many things in which 7 is a factor)+[4*Math.pow(3,5)+4*Math.pow(3,4) +4*Math.pow(3,3) +4*Math.pow(3,2) +4*Math.pow(3,1) +4*Math.pow(3,0)]

Let E be the expression in square bracket.

E = 4*(Math.pow(3,5)+Math.pow(3,4)+Math.pow(3,3)+Math.pow(3,2)+Math.pow(3,1)+Math.pow(3,0))

As you can see,its a geometric progression.

1+3+Math.pow(3,2)+Math.pow(3,3)+...........

Sn in above case for 6 terms will be,

Sn = 1*(Math.pow(3,6)-1)/(3-1)

When three digits will be repeated 6 times,

Sn = 1*Math.pow(3,18)-1)/(3-1)

In short,

Sn = 1*Math.pow(3,6m)-1)/2----------(1)where m>=1

now,to prove Math.pow(3,6m)-1 is divisible by 7, we can use induction.

For m = 1,its Math.pow(3,6)-1 which is divisible by 7-----(2)

Let it be true for m = k

so Tk = Math.pow(3,6k)-1 is divisible by 7------(3)

Now Tk+1 = Math.pow(3,6(k+1))-1

= Math.pow(3,6k+6)-1

= (Math.pow(3,6k))*Math.pow(3,6) - 1

= (Math.pow(3,6k))*Math.pow(3,6) - 1 +Math.pow(3,6)-Math.pow(3,6)

= Math.pow(3,6){Math.pow(3,6k)-1} + Math.pow(3,6)-1

By (3),left term is divisible by 7 and Math.pow(3,6)-1 is divisble by 7

Hence Tk+1 is divisible by 7

Hence expression E is divisible by 7

Hence number N is diisible by 7.

MH

It is sorta covered in the JavaRanch Style Guide. |