All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 A Great Greatest Common Divisor (Posted on 2019-03-06)
How many digits does gcd(111...111, 111...111) have?

The first number has 240 ones and the second number has 150 ones.

 No Solution Yet Submitted by Danish Ahmed Khan No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 1 of 2
The GCD is 111...111 with 30 ones.

The number with 240 1's, when divided by that with 150 1's, leaves a remainder of 111...111 with 90 1's. (The quotient is 1000...000 with 90 zeros.) It works similarly from then on in successive steps of the Euclidean algorithm.

When that with 150 1's is divided by the one with 90 1's, the remainder is that with 60 1's, and when the one with 90 1's is divided by that with 60 1's the remainder is one with 30 1's. Finally when the number consisting of 60 1's is divided by that with 30 1's the remainder is zero, indicating that that last divisor is the GCD: a number consisting of 30 ones.

 Posted by Charlie on 2019-03-06 10:46:15

 Search: Search body:
Forums (4)