It looks harmsless enough

1. Nov 15, 2005

benorin

Prove that every prime other that 2 and 5 divides infinitely many of the numbers 1, 11, 111, 1111, 11111, 111111, ...

THIS IS NOT A HOME WORK PROBLEM! So don't hold back, just put 'em out there.

2. Nov 15, 2005

shmoe

Homework or no, you're only a couple getting hints for now

If you get one of them divisible by p, you can use it to produce infinitely many.

Consider the term with p*(p-1) 1's in it. (This won't be the first one on the list, but it's the first one I thought of how to prove is divisible by p without much effort)

3. Nov 15, 2005

shmoe

Silly me, here's a much simpler way- the nth term in your sequence is just $$\frac{10^n-1}{9}$$

4. Nov 15, 2005

mathwonk

then what? little fermat? (with n = p-1)

5. Nov 16, 2005

benorin

I love you guys!

6. Nov 16, 2005

redkimchi

Suppose p is a prime that is not 2 nor 5.
A = {1, 11, 111, ...} is an infinite set.
Let B = {1 mod p, 11 mod p, 111 mod p , ...}.
B is a finite set.
Let f : A -> B be the natural function mapping each element of A to an element of B.
Since A is infinite and B is finite, there exist x > y in A such that f(x) = f(y). (Pigeon hole's principle)
Then p must divide x - y.
For example, if x is 1111111 and y is 111, then x-y is 1111*1000, so p divides 1111, because 1000 is relatively prime to p.

conclusion: p divides at least one element of A.

7. Nov 16, 2005

redkimchi

For a more stronger conclusion, let m denote 111. we denote mm = 111111, mmm = 111111111, etc.

A = {m, mm, mmm, ...} is an infinite set.
Let B = {m mod p, mm mod p, mmm mod p , ...}.
B is a finite set.
Let f : A -> B be the natural function mapping each element of A to an element of B.
Since A is infinite and B is finite, there exist x > y in A such that f(x) = f(y). (Pigeon hole's principle)
Then p must divide x - y.
For example, if x is mmmmmmm and y is mmm, then x-y is mmmm*1000000000, so p divides mmmm, because 1000000000 is relatively prime to p.

conclusion: p divides a number of the form mmm...mm. But mmm...mm is of the form 111...11 and is greater than m = 111. Therefore p divdes a number in A greater than 111.

general conclusion: p divides a number in A greater than any given number.

the general conclusion means that p divides infinitely many numbers in A.

8. Nov 16, 2005

Werg22

The only proof needed, is that if x is a prime number that is not equal to 2 or 5, b is not a finite number.

10/x = b

If b would be a finite number, with d number of digits, when multiplied by $$10^{d-1}[\tex] the result would be an integrer. Since b = 10/x, this means that [tex]\frac_{10^{d-1}(10)}{b}[\tex] would be an integrer wich imply the fact that 10^d-1 can be devided by x. Since a power has the same factors than its roots, this is impossible and thus 10/x cannot give a finite awnser. Each of these number (1,11,111...) is equal to the sum of consecutive powers of 10, such as 111 = 10^0 + 10^1 + 10^2. If devided by x, the result will be equal to the sum 10^0/x + 10^1/x + 10^2/x. By the same kind of proof, the result has to be infinite. 9. Nov 16, 2005 shmoe It seems like you're trying to show you never get an integer and therefore prove these numbers are never divisible by primes? This is obviously false. Knowing each of the terms 10^0/x, 10^1/x, 10^2/x is a non-terminating decimal (<-this is the terminology, not "infinite") does not tell you their sum is a non-terminating decimal, just take x=3 for a counterexample. 10. Nov 16, 2005 Werg22 Alright, thanks, you made realize the exeptions. To develop on that, It would be better to proove that if a and b have no common factor, the result of a/b, let say c is non-terminating, to the exeption of a = 2, 5 and b = 2, 5 a/b = c If c is terminating, with d number of digits, it would mean 10^d-1 a/b is an integrer which means that 10^d-1 has b as one of its factors. Since a power has the same factors than its roots, and 10 = 5*2, this is not possible. Thus a/b cannot be an integrer. Taking the case of the set {1, 11, 111...} Each one of this number is equal to 1 + 10^1 + 10^2...10^n and thus equal to [tex]\frac{10^n-1}{9}$$
Thus, if devided by a, the result is
$$\frac{10^n-1}{9a}$$
Since a is prime, in order for this to be terminated is that $$\frac{10^n-1}{9}$$ has a as one of its factor. So The numbers that do exeptions to the rule are the numbers that satisfy this condition.

Last edited: Nov 16, 2005