Greatest Common Factor of Numbers Composed of All OnesDate: 06/30/2008 at 01:51:17 From: Ori Subject: gcd(111..111,1111...111) I need to compute this gcd, so far I got Fibonacci numbers in the subs (the Euclidean algorithm) but I can't get to the end. Date: 06/30/2008 at 11:40:33 From: Doctor Ali Subject: Re: gcd(111..111,1111...111) Hi Ori! Thanks for writing to Dr. Math. If I understand correctly, you want to evaluate the greatest common divisor of two numbers which are made up only of 1's and they have a difference in just one 1. Please let me know if I'm on the wrong track! Firstly note that we can write, 111....111 \________/ n 1's in a more mathematical form as, 10^n - 1 ---------- 9 Do you see why? We simply subtract one from powers of ten, which makes n consecutive 9's. Dividing the result by 9 turns all the 9's into 1's. Does that make sense? I just said this so that it _may_ help us! Let's make a table of different cases that can happen. I'll make the table for, g = GCD ( 111...1 , 1111...1) \_____/ \______/ n 1's (n+1) 1's I iterated n from 1 to 10 using math software and here is the result: +-----+-----+ | n | g | +-----+-----+ | 1 | 1 | +-----+-----+ | 2 | 1 | +-----+-----+ | 3 | 1 | +-----+-----+ | 4 | 1 | +-----+-----+ | 5 | 1 | +-----+-----+ | 6 | 1 | +-----+-----+ | 7 | 1 | +-----+-----+ | 8 | 1 | +-----+-----+ | 9 | 1 | +-----+-----+ | 10 | 1 | +-----+-----+ So, it seems that they are always relatively prime! Now let's try to prove it. We know that, GCD( a , b ) = GCD( a , b - 10 a ) You can put any other number instead of 10, but in this problem, 10 helps a lot. g = GCD ( 111...1 , 1111...1) \_____/ \______/ n 1's (n+1) 1's Using the above fact, g = GCD ( 111...1 , 1111...1 - 10 x 111...1 ) \_____/ \______/ \_____/ n 1's (n+1) 1's n 1's Now, just note that the second argument equals one. So we have, g = GCD ( 111...1 , 1 ) \_____/ n 1's We know that GCD of any number and one equals one. So, g = 1 So, we proved that they are always relatively prime! Does that make sense? Please write back if you still have any difficulties. - Doctor Ali, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/