How many digits does gcd(111...111, 111...111) have?
The first number has 240 ones and the second number has 150 ones.
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 |
solution
