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

Home > Numbers
A Great Greatest Common Divisor (Posted on 2019-03-06) Difficulty: 2 of 5
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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (4)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information