Author |
Topic: Strings of 9s (Read 9379 times) |
|
James Fingas
Uberpuzzler
Gender: 
Posts: 949
|
 |
Strings of 9s
« on: Sep 5th, 2002, 11:37am » |
 Quote  Modify
|
The set of numbers {9, 99, 999, 9999, ...} has some interesting properties. One of these has to do with factorization.
Take any number n that isn't divisible by 2 or by 5. You will be able to find at least one number in the set that is divisible by n. Furthermore, you won't need to look beyond the first n numbers in the set.
Prove it.
|
| « Last Edit: Nov 7th, 2002, 11:30am by James Fingas » |
 IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
 |
Re: NEW PROBLEM: Factoring 9s
« Reply #1 on: Sep 6th, 2002, 2:35pm » |
Quote Modify
|
Very interesting! I've had a few insights but I'm still far from a solution.
|
|
IP Logged |
My arcade cabinet
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #2 on: Sep 6th, 2002, 3:16pm » |
Quote Modify
|
This follows from Fermat's little theorem: if p is a prime and a is an integer not divisible by p, then a^(p-1) - 1 is divisible by p.
If n is prime (not equal to 2 or 5), the result follows immediately by setting a = 10.
Sometimes p-1 is the smallest exponent for which p divides 10^(p-1) - 1; for example, p = 7. In other cases a smaller value suffices. Example: 333667 divides 10^9 - 1.
Otherwise, let n be a product of primes, none of which is 2 or 5. Then, for each prime, p, p divides 10^(p-1) - 1. Therefore n will divide 10^r - 1, where r is the product of all (p-1), and so r < n. (In fact, we can take r = least common multiple of all p-1.)
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #3 on: Sep 6th, 2002, 4:59pm » |
Quote Modify
|
on Sep 6th, 2002, 3:16pm, NickH wrote:This follows from Fermat's little theorem: if p is a prime and a is an integer not divisible by p, then a^(p-1) - 1 is divisible by p.
|
|
Oh yeah, I remember hearing about that. If I recall correctly, it's commonly used iteratively as a test for primality.
How tough is it to prove? I'd be interested in learning the proof.
Quote:
Otherwise, let n be a product of primes, none of which is 2 or 5. Then, for each prime, p, p divides 10^(p-1) - 1. Therefore n will divide 10^r - 1, where r is the product of all (p-1), and so r < n.
|
|
I'm feeling a bit dense... I don't see this. If n is the product of primes x and y, x divides 10x-1-1 and y divides 10y-1-1, so n divides (10x-1-1) * (10y-1-1), but I don't see how this reduces to 10(x-1)(y-1)-1.
|
|
IP Logged |
My arcade cabinet
|
|
|
Rupert
Newbie
Gender:
Posts: 11
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #4 on: Sep 6th, 2002, 5:35pm » |
Quote Modify
|
Maybe one way to prove it would be to generically construct the factor that turns n into 999.. and then show that the method always works?
For the simple case n=7 for example: We are looking for p such that n*p=999..
Working backwards:
p must end in 7. 7*7=49. 9-4=5, 7*5=35
=> p must end in 57. 7*57=399. 9-3=6, 7*8=56
=> p must end in 857. 7*857=5999. 9-5=4, 7*2=14
=> p must end in 2857. 7*2857=19999. 9-1=8, 7*4=28
=> p must end in 42857. 7*42857=299999. 9-2=7, 7*1=7
=> p must end in 142857. 7*142857=999999. Voila.
Now all that it is to show is that the method never loops, doesn't have "dead ends", and that at most n steps are needed.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #5 on: Sep 6th, 2002, 6:41pm » |
Quote Modify
|
"How tough is it to prove? I'd be interested in learning the proof."
Here's a neat proof...
http://www.utm.edu/research/primes/notes/proofs/FermatsLittleTheorem.htm l
"I'm feeling a bit dense... I don't see this. If n is the product of primes x and y, x divides 10x-1-1 and y divides 10y-1-1, so n divides (10x-1-1) * (10y-1-1), but I don't see how this reduces to 10(x-1)(y-1)-1."
I should have explained this. It follows from 10^ab - 1 = (10^a - 1)(10^(ab-a) + 10^(ab-2a) + ... + 1). Example: 10^15 - 1 = (10^3 - 1)(10^12 + 10^9 + 10^6 + 10^3 + 1). The sum of a geometric progression!
|
| « Last Edit: Sep 6th, 2002, 6:43pm by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #6 on: Sep 7th, 2002, 12:58pm » |
Quote Modify
|
on Sep 6th, 2002, 3:16pm, NickH wrote:| This follows from Fermat's little theorem |
|
I had an answer that starts from the more general Euler's theorem: aphi(n) = 1 (mod n) when a and n are relatively prime, and where phi(n) is the number of numbers <= n and relatively prime to n (includes 1).
We want to show that for all n there exists an m <= n such that 10m = 1 (mod n). Since n is not divisible by 2 or 5, Euler's theorem says that this is satisfied by m = phi(n). phi(n) must be <= n, so this satisifes the other constraint.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #7 on: Sep 9th, 2002, 5:54am » |
Quote Modify
|
Ye, this one is pretty easy if you know any number theory.
Jon, here's a really easy proof (without having followed the link James sent, so hope I'm not being redundant): Take U the set of units [divisors of 1] in Zn [the ring of remainders wrt n] -- in this case it is just the numbers rel prime to n. For ANY unit u, the mappinf f:U->U defined by f(x)=ux is a bijection (pf left to reader but is easy). That means the product of all elements of U is equal to the product of all elements of uU, which is u^|U| times the product of all elements of U. Therefore u^|U| = 1 (mod n). It happens that for n prime |U|=p-1, and in general is phi(n) as SOwen mentioned.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #8 on: Sep 9th, 2002, 11:25am » |
Quote Modify
|
Very good work!
NickH,
I am still a little confused by your post. Please explain how it relates to the number 49, which factors 1042-1. I cannot figure out how your answer predicts this.
Could you make the variables a little clearer? All the n's, p's, and a's are making my head spin
Rupert,
I like your solution. It's similar to my solution. Do you notice anything about the string of digits "142857"??
S. Owen,
Very good. Too bad I didn't make you try harder...
Eric,
 I wish I understood that ... no, on second thought, I'm happy not understanding!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #9 on: Sep 9th, 2002, 11:31am » |
Quote Modify
|
Sorry I didn't explain more clearly... I'm happy to clarify if there's a specific point?
(I haven't read closely to see what you guys are talking about, but yep: 142857 looks suspiciously like 1/7 I'm guessing that's the reference.)
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #10 on: Sep 9th, 2002, 11:44am » |
Quote Modify
|
on Sep 9th, 2002, 5:54am, Eric Yeh wrote:| Jon, here's a really easy proof (without having followed the link James sent, so hope I'm not being redundant): |
|
Yeah, NickH's link about Fermat's little theorem offers a proof that is a special case of Eric's proof. It is considering only prime values of n, so Zn is just the numbers 1 through n-1, and so I find the proof easier to follow as it is more concrete. Reading the proof there will make Eric's more general one seem actually unintimidating.
|
| « Last Edit: Sep 9th, 2002, 2:04pm by S. Owen » |
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #11 on: Sep 9th, 2002, 12:24pm » |
Quote Modify
|
Damn!! jk, I thought it was more accessible, sorry.
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #12 on: Sep 9th, 2002, 1:15pm » |
Quote Modify
|
Eric,
This is the part I didn't get:
on Sep 9th, 2002, 5:54am, Eric Yeh wrote:
Take U the set of units [divisors of 1] in Zn [the ring of remainders wrt n] -- in this case it is just the numbers rel prime to n. For ANY unit u, the mappinf f:U->U defined by f(x)=ux is a bijection (pf left to reader but is easy). That means the product of all elements of U is equal to the product of all elements of uU, which is u^|U| times the product of all elements of U. Therefore u^|U| = 1 (mod n). It happens that for n prime |U|=p-1, and in general is phi(n) as SOwen mentioned.
|
|
The "divisors of 1" has me stumped ... are we talking complex numbers here? 1/1 = 1 ...
I think I understand what the "ring of remainders" is--just all the numbers smaller than n (since any of them could be a remainder when you divide by n).
For a "unit" u, the mapping U-->U given by f(x)=ux is a "bijection". I know u is an element of U. It looks like we're multiplying all the elements in U by u, and that somehow this leaves the product of the elements of U unchanged. If only I knew what a bijection was...
And then I got confused ... err, more confused
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #13 on: Sep 9th, 2002, 1:30pm » |
Quote Modify
|
James,
1. Formally, in a system R, u \in R is a unit (divisor of 1) if there exists another elemt k \in R such that uk = 1. For example, in Z10, the ring of remainders mod 10 (sorry I'm too lazy to subscript the 10, but it should be), 3 is a unit because there exists the number 7 such that 3*7 = 21 = 1 (mod 10). In Zn, the set of units is precisely represented by the numbers between 1 and n-1 which are relatively prime to n. (This is equivalent to the Diophantine Result: given integers a and b, the equation ax+by=1 has integer solns iff (a,b)=1, ie they are rel prime.)
2. Yes, your intuition for ring of remainders is roughly correct. (Without going into detail, the "system" R I use in 1. above is actually a "ring", too.)
3. A bijection is just a 1-1 identification of all elements of two sets. For example, there is a bijection between {1,2,3} and {a,b,c}. The important thing here is that multiplying all units \in U by u gives you back the same set -- therefore the product is the same. (In general, you can show that a mapping f is a bijection iff it is 1) well-defined; 2) one-to-one (aka 1-1 or injective); and 3) onto (aka surjective)).
Let me know if you need further defns. Can I ask your background? It might help me better express these concepts.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #14 on: Sep 9th, 2002, 1:55pm » |
Quote Modify
|
BTW NickH,
Be careful, your proof doesn't work when n contains square primes (I just looked at your proof). You only get single power divisors, never any higher powers of p.
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #15 on: Sep 9th, 2002, 2:10pm » |
Quote Modify
|
Eric,
Thanks. My background is in electrical engineering, so I would say I understand polynomials, matrices, linear equations, etc, but very little number theory. For instance, modulo-multiplication is a little scary...
I think I am getting you now. Is this what you're saying?
1) For every number n (in this example, 10), there's the ring of remainders 1, 2, ... 9. Some of these numbers are "units", and belong to the set U. You can tell which ones are units because units have the property that for some number a, (u*a) mod n = 1. That's why they're called "divisors of 1", or "units".
2) U can only include numbers co-prime to n, because it's easy to see that anything that factors n can't be a "unit".
3) If we can prove that everything in Zn which is coprime to n is also in U, then we're done. But this doesn't seem to be the route you take.
4) Instead, you show that when you multiply all the numbers in U by any u (an element of U), you get back all the numbers in U. Thus the product of all the elements is the same before and after.
5) However, you have (mod n) multiplied by u|U|, where |U| is the number of elements in U. So it would appear that u|U| mod n is 1. Which is what we wanted to show in the first place!
If I got that wrong, then give up on me now because there's no hope...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
 |
Re: NEW PROBLEM: Factoring 9s
« Reply #16 on: Sep 9th, 2002, 2:14pm » |
Quote Modify
|
Eric,
Thanks, I see that now! I'm hoping there is a way to rescue the proof, as the initial step, for primes only, seems quite economical. Or will this road inevitably lead to S. Owen's proof?
What's your background, by the way?
Nick
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #17 on: Sep 9th, 2002, 2:26pm » |
Quote Modify
|
James,
You're basically there, but let me make some minor comments:
1) There is also 0. Otherwise, everything's right.
2) Yup.
3) This is true, but Im not sure where you are getting "then we're done" or that I'm not using it. I [i]do[/] use it, and I assume the pf based on the Diophantine Result. I need it because otherwise I can't say that 10 is a unit in Zn.
Out of curiosity, why would you say we were done?
4) Precisely.
5) Exactly. Here one should be careful to note that we require commutativity, and also cancellation by units: au=bu => a=b, precisely because u is a unit. Note that this is not as trivial as it is in the integers, or the reals!!! It does not hold in general Zn. Witness: 1*2 = 4*2 (mod 6), but 1 != 4!!!!! So we are lucky in some sense that this works out...
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #18 on: Sep 9th, 2002, 2:30pm » |
Quote Modify
|
on Sep 6th, 2002, 5:35pm, Rupert wrote:| For the simple case n=7 for example: We are looking for p such that n*p=999.. |
|
on Sep 9th, 2002, 11:31am, Eric Yeh wrote:| I haven't read closely to see what you guys are talking about, but yep: 142857 looks suspiciously like 1/7 |
|
Yeah, we are looking for p such that np = 999...9, or alternatively, such that 1/n = p/999...9. Since 1/7 is the repeating decimal 0.142857142857... = 142857/999999, we know that 7*142857=999999.
1/n will be a repeating decimal if n isn't divisble by 2 or 5, and so the same construction can be used for any such n. What's not yet clear to me is how you can prove that it 1/n repeats in <= n digits, but since it's true, I'm sure you can!
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #19 on: Sep 9th, 2002, 2:31pm » |
Quote Modify
|
on Sep 9th, 2002, 2:14pm, NickH wrote:Eric,
Thanks, I see that now! I'm hoping there is a way to rescue the proof, as the initial step, for primes only, seems quite economical. Or will this road inevitably lead to S. Owen's proof?
What's your background, by the way?
Nick |
|
Nick,
Ye, that route is most easily generalizable by going the SOwen route (Also the one I've been discussing with James). But don't despair; it's just as elegant and is only a tiny bit harder! So you've pretty much got it.
Me? Hehe, I'm a big mystery. I can't tell you now, otherwise I won't be able to post that as a NEW PROBLEM sometime down the line. It should be deduced from the sum totality of my previous posts.
Best,
Eric
|
| « Last Edit: Sep 9th, 2002, 2:35pm by Eric Yeh » |
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #20 on: Sep 9th, 2002, 2:34pm » |
Quote Modify
|
on Sep 9th, 2002, 2:30pm, S. Owen wrote:
Yeah, we are looking for p such that np = 999...9, or alternatively, such that 1/n = p/999...9. Since 1/7 is the repeating decimal 0.142857142857... = 142857/999999, we know that 7*142857=999999.
1/n will be a repeating decimal if n isn't divisble by 2 or 5, and so the same construction can be used for any such n. What's not yet clear to me is how you can prove that it 1/n repeats in <= n digits, but since it's true, I'm sure you can! |
|
Dude, if nothing else, we've proven it with our phi(n) pf! But ye, perhaps there's a more elementary pf... Nah, I don't think so.
Best,
Eric
How strange, never in all my prev posts has someone "inter-posted" me, but it just happened twice here on this thread!! 
|
| « Last Edit: Sep 9th, 2002, 2:34pm by Eric Yeh » |
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #21 on: Sep 9th, 2002, 2:38pm » |
Quote Modify
|
Ok ok better write fast before someone inter-posts me again and then I look like an idiot: the repeating thing is obvious, just look at the number of different remainders there can be when you do the long division. It can't be more than n...
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #22 on: Sep 10th, 2002, 1:25pm » |
Quote Modify
|
Eric,
When I said that we were done if all numbers coprime to n were units, I was thinking of my question as asking about units. However, this isn't really true, since I'm only considering certain muliples of 10. For instance 3 is a unit because 3*7=1, but this doesn't help us in this case, because we only consider 10i, not 10*i. The two have identical answers, but it would take more work to show that. Also, I'm asking for a remainder of -1, not a remainder of 1.
Silly me 
SOwen,
Your proof is looking very similar to mine ... and Eric has so nicely pointed out why the decimal representations have to repeat after <n digits.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #23 on: Sep 10th, 2002, 1:33pm » |
Quote Modify
|
Right. (BTW, I didn't want to make an unprecedented FOUR posts in a row yesterday, but right after seeing the repeat argument and rushing to post it, I also realized that you can also get the same (stronger) phi(n) bound (using the division argument)!! Pf is left as an exercise to the reader ).
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: NEW PROBLEM: Factoring 9s
« Reply #24 on: Sep 11th, 2002, 8:21pm » |
Quote Modify
|
A bit off topic, but I can't resist a challenge.
Quote:| Me? Hehe, I'm a big mystery. I can't tell you now, otherwise I won't be able to post that as a NEW PROBLEM sometime down the line. It should be deduced from the sum totality of my previous posts. |
|
From the fact that your posts date from way back, I deduce that you have some connection with Berkeley. From the fact that all your posts have the name "Eric Yeh" to the left of them, and that's not an obvious Internet pseudonym, I deduce that your name is Eric Yeh. From the fact that your e-mail address is at Harvard, I deduce that you have some connection with Harvard. A minute or two with Google and some simple deductions, and we have that you were an undergrad at Berkeley, possibly in computer science, then a grad student at Harvard, and currently a programmer.
Or did you mean from the content of your posts?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print