Author 
Topic: Strings of 9s (Read 7773 times) 

James Fingas
Uberpuzzler
Gender:
Posts: 949


Strings of 9s
« on: Sep 5^{th}, 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 7^{th}, 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 6^{th}, 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 6^{th}, 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^(p1)  1 is divisible by p. If n is prime (not equal to 2 or 5), the result follows immediately by setting a = 10. Sometimes p1 is the smallest exponent for which p divides 10^(p1)  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^(p1)  1. Therefore n will divide 10^r  1, where r is the product of all (p1), and so r < n. (In fact, we can take r = least common multiple of all p1.) Nick


IP Logged 
Nick's Mathematical Puzzles



Jonathan_the_Red
Junior Member
Gender:
Posts: 102


Re: NEW PROBLEM: Factoring 9s
« Reply #3 on: Sep 6^{th}, 2002, 4:59pm » 
Quote Modify

on Sep 6^{th}, 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^(p1)  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^(p1)  1. Therefore n will divide 10^r  1, where r is the product of all (p1), 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 10^{x1}1 and y divides 10^{y1}1, so n divides (10^{x1}1) * (10^{y1}1), but I don't see how this reduces to 10^{(x1)(y1)}1.


IP Logged 
My arcade cabinet



Rupert
Newbie
Gender:
Posts: 11


Re: NEW PROBLEM: Factoring 9s
« Reply #4 on: Sep 6^{th}, 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. 94=5, 7*5=35 => p must end in 57. 7*57=399. 93=6, 7*8=56 => p must end in 857. 7*857=5999. 95=4, 7*2=14 => p must end in 2857. 7*2857=19999. 91=8, 7*4=28 => p must end in 42857. 7*42857=299999. 92=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 6^{th}, 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 10x11 and y divides 10y11, so n divides (10x11) * (10y11), but I don't see how this reduces to 10(x1)(y1)1." I should have explained this. It follows from 10^ab  1 = (10^a  1)(10^(aba) + 10^(ab2a) + ... + 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 6^{th}, 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 7^{th}, 2002, 12:58pm » 
Quote Modify

on Sep 6^{th}, 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: a^{phi(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 10^{m} = 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 9^{th}, 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=p1, 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 9^{th}, 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 10^{42}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 9^{th}, 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 9^{th}, 2002, 11:44am » 
Quote Modify

on Sep 9^{th}, 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 Z_{n} is just the numbers 1 through n1, 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 9^{th}, 2002, 2:04pm by S. Owen » 
IP Logged 



Eric Yeh
Senior Riddler
Gender:
Posts: 318


Re: NEW PROBLEM: Factoring 9s
« Reply #11 on: Sep 9^{th}, 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 9^{th}, 2002, 1:15pm » 
Quote Modify

Eric, This is the part I didn't get: on Sep 9^{th}, 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=p1, 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" isjust 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 9^{th}, 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 n1 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 11 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) welldefined; 2) onetoone (aka 11 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 9^{th}, 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 9^{th}, 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, modulomultiplication 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 coprime 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 9^{th}, 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 9^{th}, 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 9^{th}, 2002, 2:30pm » 
Quote Modify

on Sep 6^{th}, 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 9^{th}, 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 9^{th}, 2002, 2:31pm » 
Quote Modify

on Sep 9^{th}, 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 9^{th}, 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 9^{th}, 2002, 2:34pm » 
Quote Modify

on Sep 9^{th}, 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 "interposted" me, but it just happened twice here on this thread!!

« Last Edit: Sep 9^{th}, 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 9^{th}, 2002, 2:38pm » 
Quote Modify

Ok ok better write fast before someone interposts 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 10^{th}, 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 10^{i}, 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 10^{th}, 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 11^{th}, 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 email 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 



