wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Strings of 9s
        
(Message started by: James Fingas on Sep 5^th, 2002, 11:37am)

Title: Strings of 9s
Post by James Fingas on Sep 5^th, 2002, 11:37am

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.

Title: Re: NEW PROBLEM: Factoring 9s
Post by Jonathan_the_Red on Sep 6^th, 2002, 2:35pm

Very interesting! I've had a few insights but I'm still far from a solution.

Title: Re: NEW PROBLEM: Factoring 9s
Post by NickH on Sep 6^th, 2002, 3:16pm

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by Jonathan_the_Red on Sep 6^th, 2002, 4:59pm

on 09/06/02 at 15:16:43, 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 10^x-1-1 and y divides 10^y-1-1, so n divides (10^x-1-1) * (10^y-1-1), but I don't see how this reduces to 10^(x-1)(y-1)-1.

Title: Re: NEW PROBLEM: Factoring 9s
Post by Rupert on Sep 6^th, 2002, 5:35pm

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.
;)

Title: Re: NEW PROBLEM: Factoring 9s
Post by NickH on Sep 6^th, 2002, 6:41pm

"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.html

"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!

Title: Re: NEW PROBLEM: Factoring 9s
Post by S. Owen on Sep 7^th, 2002, 12:58pm

on 09/06/02 at 15:16:43, 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.

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 5:54am

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by James Fingas on Sep 9^th, 2002, 11:25am

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⁴²-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!

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 11:31am

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by S. Owen on Sep 9^th, 2002, 11:44am

on 09/09/02 at 05:54:41, 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 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.

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 12:24pm

Damn!! ;) jk, I thought it was more accessible, sorry.

Title: Re: NEW PROBLEM: Factoring 9s
Post by James Fingas on Sep 9^th, 2002, 1:15pm

Eric,

This is the part I didn't get:

on 09/09/02 at 05:54:41, 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

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 1:30pm

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 1:55pm

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by James Fingas on Sep 9^th, 2002, 2:10pm

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...

Title: Re: NEW PROBLEM: Factoring 9s
Post by NickH on Sep 9^th, 2002, 2:14pm

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 2:26pm

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by S. Owen on Sep 9^th, 2002, 2:30pm

on 09/06/02 at 17:35:14, Rupert wrote:

For the simple case n=7 for example: We are looking for p such that n*p=999..

on 09/09/02 at 11:31:05, 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!

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 2:31pm

on 09/09/02 at 14:14:50, NickH wrote:

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 2:34pm

on 09/09/02 at 14:30:04, S. Owen wrote:

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!! :P

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 9^th, 2002, 2:38pm

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by James Fingas on Sep 10^th, 2002, 1:25pm

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ⁱ, 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.

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 10^th, 2002, 1:33pm

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

Title: Re: NEW PROBLEM: Factoring 9s
Post by Chronos on Sep 11^th, 2002, 8:21pm

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? ;)

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 11^th, 2002, 9:37pm

Heehee, you're so funny Chronos! I meant it as a joke, but since you are taking it seriously, I guess I can too!!! ;) So how SURE are you of your guesses? Surely there are multiple "Eric Yeh"s that appear on your Google search? Can't my early posts simply be due to a fanaticism in puzzles?? And can you ascertain my studies or current work? (Your hypotheses seem unsubstantiated at the moment -- and you didn't even hypothesize my [supposed] graduate work!) Where'd the currently programming note come from? And I did indeed mean based on the content of my posts, but your resourcefulness is noted!! ;)

Not a bad start though! Should I post this as a "real" problem??! ;) ;) ;) JK!!! (Seriously.)

Best,
Eric

Title: Re: NEW PROBLEM: Factoring 9s
Post by TimMann on Sep 11^th, 2002, 10:45pm

Here's a more elementary proof. It uses only the pigeonhole principle and the unique factorization theorem.

Assume that none of the integers in the set S_n = {10¹-1, ..., 10ⁿ-1} is divisible by n, where n is not divisible by 2 or 5. By the pigeonhole principle, at least two of these integers must have the same remainder when divided by n -- there are n integers in the set, and only n-1 distinct remainders available since 0 has been ruled out. Let 10^j-1, 10^k-1 be one such pair, with n >= j > k > 0. Then n divides their difference, (10^j-1) - (10^k-1) = 10^j - 10^k = (10^j-k - 1)(10^k). That is, there exists an integer m such that mn = (10^j-k - 1)(10^k).

Consider the prime factorization of each side of this equation. By the unique factorization theorem, each of the 2's and 5's that make up the factorization of the 10^k on the right must appear in the factorization of either n or m on the left. But we are given that n is not divisible by 2 or 5, so all the factors must come from m. Thus we know that m' = m/10^k is an integer, and m'n = 10^j-k - 1. But j-k < n, so 10^j-k - 1 is an element of S_n. This contradicts our assumption that no such numbers are divisible by n.

Therefore there exists an element of S_n that is divisible by n.

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 12^th, 2002, 5:52am

Tim,

Nice pf -- it also easily generalizes to the sharper bound of phi(n). I should mention, however, that while UFT is perhaps a more intuitive concept, a true proof of it from basic principles is no more elementary than our previous proof. In fact, the most direct path generally leads through the Diophantine Result as well, and then requires one more "big step" to get the UFT.

Best,
Eric

Title: Re: NEW PROBLEM: Factoring 9s
Post by Chronos on Sep 15^th, 2002, 10:29pm

Quote:

So how SURE are you of your guesses?

I'm not SURE in a physicist's sense of SURE, but then, a physicist never is that sure. And I figured you were joking, but it was fun to play along.

As for the specifics: I found a mention of an "Eric Yeh" at Berkeley, in a CS paper on the construction of an image wand. The Harvard connection was a page on "Where are math grads now?", which listed an "Eric Yeh" as currently being a programmer. Based on the dates for these two references, I suspected that Berkeley was undergrad and Harvard was grad. There might be multiple folks named "Eric Yeh", but how many could there really be associated with Harvard, and with a strong mathematical inclination?

And based on the content of posts alone, I would have guessed programmer or mathematician anyway.

Title: Re: NEW PROBLEM: Factoring 9s
Post by Eric Yeh on Sep 16^th, 2002, 12:34pm

Chronos,

Fair enough. However, I have no affiliation with Berkeley. And worse yet, only five fingers on my left hand.

Happy Puzzling, ;)
Eric

Title: Re: Strings of 9s
Post by titan on Oct 16^th, 2013, 7:57am

Can somebody please prove this:
1/n will be a repeating decimal if n is not divisible by 2 or 5

Title: Re: Strings of 9s
Post by pex on Oct 16^th, 2013, 8:58am

on 10/16/13 at 07:57:15, titan wrote:

Can somebody please prove this:
1/n will be a repeating decimal if n is not divisible by 2 or 5

Long division algorithm + pigeonhole principle.

Title: Re: Strings of 9s
Post by Grimbal on Oct 16^th, 2013, 9:37am

It will also be repeating if it is divisible by 2 or 5. You just have to write out the '0's: 1/4 = 0.25000... .
Even without being divisible by 2 or 5, there is already the case of n=1: 1/n = 1.000... .

Title: Re: Strings of 9s
Post by Dmitriy on May 12^th, 2014, 3:14pm

Here is a simple solution to the original problem.

Suppose among the first n numbers 9, 99, 999, ... there are no numbers divisible by n. Then at least two of these numbers (e.g. 99 and 99999) must have the same remainder when divided by n. Subtracting them, we get a number (e.g.99900) divisible by n. But because n does not contain factors of 2 and 5, that would mean 999 is divisible by n. Done!