Uncovering the Mystery of Numbers Divisible by 7

[mahesh_2961]

hi ,
i recently found while playing around with my new calculator that any number repeated six times is divisible by 7 ...
for eg, 4 repeated 6 times gives 444444/7 =63492
an say 761 repeated 6 times 761761761761761761/ 7 =108823108823108823
the last one was done using a computer ...
can anyone please help me out why this happens?

regrds
Mahesh

 

[mahesh_2961]

one correction to my query ... not any number but any integer
sorry for that

Mahesh

 

[Zurtex]

227153715052227153715052227153715052227153715052227153715052227153715052 is 227153715052 repeated 6 times and is not a multiple of 7 as its prime factors are:

2 ^ 2 x 3 x 11 x 19 x 37 x 67 x 73 x 137 x 3169 x 52579 x 98641 x
333667 x 2082527 x 99990001 x 999999000001 x 3199044596370769

Edit: Sorry got a little carried away on my computer

 

[mahesh_2961]

hi ,
repeating an integer, x (say), six times is not the same as multiplying it six times ...
i m sorry but i think u haven't got my question correctly...
it is like this
suppose x is an n digit number
repeating it 6 times gives a number
y= 1*x + 10^(n)*x + 10^(2n)*x + 10^(3n)*x+ ...+10^(6n)*x
which is not equal to x^6
and i think i have got the solution for this problem...
if u want me to post it please tell me , or if u want to find it urself then its good for u

regards
Mahesh

 

[gonzo]

well, it's easy to prove for anyone digit number n:

10^5*n+10^4*n+10^3*n+10^2*n+10*n+n

That is a single digit n repeated 6 times, divide by 7 and you get:

14285 5/7 * n +
1428 4/7 * n +
142 6/7 * n +
14 2/7 * n +
1 3/7 * n +
1/7 * n =

15870*n + (21/7)*n = 15873 * n

So, a single digit repeated 6 times will always divide by 7 to an integer. In other words, if you multiply 15873 * 7 * n , where n is a single digit, then you will get a number that is that digit repeated 6 times.

If you feel like it, you can attempt similar proofs for more than one digit to see if it holds for more than one digit repeated, and if not than maybe you can find certain conditions for which it would hold with bigger numbers.

Or maybe someone has a better way to prove this than me ...

 

[Muzza]

It does not appear to be true for 123423123423123423123423123423123423 either (that is 123423 repeated 6 times).

 

[matt grime]

Repeating a string, s, of r digits six times is the sam as the sum of a geometric progression. Let k be 10^r, it is

s +ks +k^2s+..+k^5s

The sum of this is (s/9)*(10^6-1)

since 9=2 mod 7, and thus invertible, and 10 is coprime with 7, this reduces to zero mod 7 quite trivially by fermat's little theorem.

 

[gonzo]

hi ,
repeating an integer, x (say), six times is not the same as multiplying it six times ...
i m sorry but i think u haven't got my question correctly...
it is like this
suppose x is an n digit number
repeating it 6 times gives a number
y= 1*x + 10^(n)*x + 10^(2n)*x + 10^(3n)*x+ ...+10^(6n)*x
which is not equal to x^6
and i think i have got the solution for this problem...
if u want me to post it please tell me , or if u want to find it urself then its good for u

regards
Mahesh

You do realize this post doesn't make much sense, do you? First, the person you responded to didn't multiple a number 6 times, he/she did what you did, and just repeated one.

And your formula is wrong. It should only go up to 10^(5n).

 

[gonzo]

since 9=2 mod 7, and thus invertible

Matt, could you explain this snippet a bit more for me? I've done some modular arithmatic to determine factorability, but this loses me. Thanks.

 

[Zurtex]

hi ,
repeating an integer, x (say), six times is not the same as multiplying it six times ...

227153715052227153715052227153715052227153715052227153715052227153715052 is 227153715052 repeated 6 times and not (227153715052)⁶ and it is not a multiple of 7.

 

[matt grime]

Either you or I have made a mistake, then, Zurtex. Now, if there truly were counter examples, then there would be a smaller on than the one you've just written. Incidentally, what is the remainder of that number mod 7?

As for dividing by 9.

suppose x/9 = y in the integers, then x=9y, and x=9y mod any integer, n say. If 9 and n are relativeyl prime then there is an integer k such that 9k=1 mod n thus xk=y mod n. 9 is a unit modulo 9, 9 is invertible. If 9 and 7 weren't coprime then I couldn't do this.

 

[gonzo]

okay, I followed everything you said individually, but I don't understand "invertible".

I'm missing some piece of the puzzle here. Sorry for being dense. Maybe you could write it out in few steps starting from

s/9 * (10^6 -1)

I would start like this myself (which seems to be more complicated and possibly wrong):

10^6=10^3*10^3 and 10^3 mod 7 = -1

so the whole thing mod 7 = s/9(-1*-1 -1) = 0

 

[shmoe]

Repeating a string, s, of r digits six times is the sam as the sum of a geometric progression. Let k be 10^r, it is

s +ks +k^2s+..+k^5s

The sum of this is (s/9)*(10^6-1)

since 9=2 mod 7, and thus invertible, and 10 is coprime with 7, this reduces to zero mod 7 quite trivially by fermat's little theorem.

Your geometric series should be s/(k-1)*(k^6-1)

k-1 won't be invertible mod 7 if r=0 mod 6 (Fermat's little theorem). Note Zurtex example has r=12 and Muzza has r=6. r=6 is the least number of digits you'll find for a counterexample.

 

[matt grime]

ah, there we go, for some reason i'd got 9 rather than 10^r - 1.

 

[Ethereal]

I think mahesh really meant the following as he himself corrected:

one correction to my query ... not any number but any integer
sorry for that

But in any case, what range of number string lengths can be repeated six times and be divisible by 7?

 

[dextercioby]

But in any case, what range of number string lengths can be repeated six times and be divisible by 7?

I believe Shmoe's post was pretty clear.Basically any natural number except natural multiples of 6.

Daniel.

 

[gonzo]

k-1 won't be invertible mod 7 if r=0 mod 6 (Fermat's little theorem).

Is this because 10^6 mod 7 = 1 so that k-1=0?

Can someone give me a really simple definition of "invertible" here? Thanks.

 

[Zurtex]

I've not been able to keep up the thread but I think you're in the wrong matt:

227153715052227153715052227153715052227153715052227153715052227153715052 mod 7 = 2

There will be smaller counter examples but that's the 1st one I found (mind you I only searched for about 10 secs.

 

[mahesh_2961]

hai ,
u ppl were right... when i found one of the solutions for the problem ... i thought it was quite an easy one ... and u rightly pointed out the mistake i made in the formula ...
i apologize for anything from my side...

This cannot be called a proof...
i noted that (1/7) = 0.142857142857142857... with '142857' reccuring so
y= 1*x + 10^(n)*x + 10^(2n)*x + 10^(3n)*x+ 10^(4n)*x +10^(5n)*x
=x(1+10^n+10^2n+10^3n+10^4n+10^5n)
Now i multiplied both sides with 0.142857142857...
and found that RHS is always an integer irrespective of the values of x and hence n.
thank u guys for helping me

cheers
Mahesh

 

[matt grime]

I've not been able to keep up the thread but I think you're in the wrong matt:

227153715052227153715052227153715052227153715052227153715052227153715052 mod 7 = 2

There will be smaller counter examples but that's the 1st one I found (mind you I only searched for about 10 secs.

yep. i am, and shmoe has pointed out where my error is.

 

[Galileo]

I've not been able to keep up the thread but I think you're in the wrong matt:

227153715052227153715052227153715052227153715052227153715052227153715052 mod 7 = 2

There will be smaller counter examples but that's the 1st one I found (mind you I only searched for about 10 secs.

Muzza found 123423 repeated six times.
It factors into $(3)^2(19)(101)(999999000001)(333667)(52579)(41141)(9901)$

Repeating 123422 gives a smaller one

 

[Zurtex]

Muzza found 123423 repeated six times.
It factors into $(3)^2(19)(101)(999999000001)(333667)(52579)(41141)(9901)$

Repeating 123422 gives a smaller one

Good good but I was the 1st reply (other than the original poster) with this counter example, there was no need for all of this nonsense

 

[Muzza]

And 100000 repeating smaller yet... ;)

 

[matt grime]

Good good but I was the 1st reply (other than the original poster) with this counter example, there was no need for all of this nonsense

at least we have established a sufficient condition for it to be true though (however not necessary).

 

[shmoe]

Is this because 10^6 mod 7 = 1 so that k-1=0?

That's correct.

Can someone give me a really simple definition of "invertible" here? Thanks.

we say s is invertible mod n if there exists a t with st=1 mod n. You can show that s is invertible mod n if and only if s and n have no common factors except 1 (they're relatively prime). In this case you can find the inverse by using the Euclidean algorithm to write 1 as a linear combination of s and n. Thus for 9 mod 7:

9=7*1+2
7=2*3+1

Turning this around we get:

1=7-2*3=7*4+(-3)*9

And we see (-3)*9=4*9=1 mod 7

so 9 is invertible mod 7 and it's inverse is 4. Of course you could have found this inverse by inspection easily enough, but the euclidean algortihm will work for the general case.

 

[shmoe]

at least we have established a sufficient condition for it to be true though (however not necessary).

Necessary should be easy enough. If s has r=6t digits and is repeated 6 times. k=10^r as before. k=1 mod 7 so

s+s*k+s*k^2+...s*k^5=s*6 mod 7

If this were to be zero mod 7, then we must have s=0 mod 7.

Therefore if you repeat a number s with 6t digits 6 times it is divisible by seven if and only if s is divisible by 7.

 

[gonzo]

Your geometric series should be s/(k-1)*(k^6-1)

k-1 won't be invertible mod 7 if r=0 mod 6 (Fermat's little theorem). Note Zurtex example has r=12 and Muzza has r=6. r=6 is the least number of digits you'll find for a counterexample.

Thanks shmoe! I understand the idea of invertible now, how to find it and what it means in general. What I still don't understand though is why it matters that "k-1" in your exmaple above is just invertible. My attempt at undersanding earlier had more to do with dividing by 0 being a bad thing. What is the direct consequence of k-1 being or not being invertible in the above situation? thanks.

 

[matt grime]

Let us do another example with real numbers.

3 is not invertible mod 6 so we cannot conclude that 3x=0 mod 6 is equivalent to x=0 mod 6. essentially we were looking at something like ax/b. in a case like this, if a and b are coprime with n then ax/b=0 mod n is equivalent to x=0 mod n. Ie we can cancel.

 

[shmoe]

Thanks shmoe! I understand the idea of invertible now, how to find it and what it means in general. What I still don't understand though is why it matters that "k-1" in your exmaple above is just invertible. My attempt at undersanding earlier had more to do with dividing by 0 being a bad thing. What is the direct consequence of k-1 being or not being invertible in the above situation? thanks.

We had the series s*(1+k+k^2+...+k^5). Now this is a geometric series and we know

(k-1)(1+k+...+k^5)=(k^6-1)

This will hold mod anything we like. We'd like to divide by k-1. It's better to think of division as multiplication by the multiplicative inverse (note 0 does not have an inverse). In the case when k=1 mod 7, you're hooped since 0 does not have a multiplicative inverse.

Now your reasoning about not being able to divide by zero is perfectly fine here. If our modulus is not prime though, there are non-zero things that won't have multiplicative inverses, like 3 mod 9 for example. The preferred language here is "3 does not have a multiplicative inverse mod 9" rather than "we can't divide by 3 mod 9".

 

[gonzo]

Thanks, I think I understand. Is this a specific case of something more general--that you can not solve modular equations where you divide by a number that doesn't have an inverse mod that number?

Is dividing my a number without an ineverse in that "mod space" just always undefined?

Or is it saying something more integer related?

So for example, if we divide by 3 mod 9, are we saying that this is like dividing by zero in "normal" math?

 

[matt grime]

as shmoe says, you do not "divide by 3 mod 9"

 

[gonzo]

Okay, thanks I think, though I would have liked a more direct answer. I am assuming you mean that division is always thought of as multiplication by the inverse instead, and since that inverse doesn't exist you are multiplying by something that doesn't exist, and so the whole thing is undefined. Which means it is like dividing by 0 in that sense.

Is this correct?

 

[shmoe]

yes, that's a fair summary.

 

[matt grime]

note that in the case of non-unit elements there may or may not be solutions to ax=b mod n, and let us assume b=/=0

suppose a is not invertible mod n, but that b is, with inverse c say, the a(xc)=1mod n, contradicting the assumption that a is not invertible.

so *if* there is a solution it is necessary that b is not invertible either. so for example

2x=5 mod 6 has no solutions

2x=4 mod 6 does have a solution though, but 2x=3 doesn't, so all other possibilties can arise.

to see what's going on it can somte times be useful to think of u=v mod n as saying v=mn+v for some integer m.

so, ax=b mod n says ax=mn+b for some m. rearranging ax-mn=b


of course hcf(a,n) divides the lhs [hightest common factor, so if there were a solution then it mustbe that the hcf divides the rhs, ie b.

this is why 2x=3 mod6 has no solution: hcf(2,6)=2 and 2 doesn't divide 3.

Can you see where that's going?


This also shows you that a number is invertibel mod n if and only if it is coprime with n.

If a is coprime with n, then by euclid's algorothm ap+nq=1 for some n and q, hence ap=1 mod n, that is p is the mutliplicative inverse of a.