Find the gcd or hcf of (111111..11hundred times) and (1111..11sixty times)?

Question

Find the gcd or hcf of (111111..11hundred times) and (1111..11sixty times).
(a) 111..forty ones
(b) 111..twenty five ones
(c) 111..twenty ones
(d) None of these

Answer 1

d) None of these, since each successive term is 10 times the previous one plus 1, so larger terms can never be exactly divisible by any of the smaller terms except the first, which is unity.

The HCF must be 1.

Answer 2

The previous respondants argument is incorrect. The problem with it is that if we look at 1111...1 repeated n times and 1111...1 repeated n-1 times, then he/she is correct that the HCF is 1, since the former is the latter number times n + 1. But this only shows that if you consider the list of numbers of this type with n digits with n going from 1, 2, 3, ... etc. to infinity (these are called repunits, by the way), then each number is not divisible by the previous. It doesn't show that each of these numbers cannot be divisible by a number much earlier in the list, however.

To find the HCF, we don't want to try to factor these huge numbers, so we use the Euclidean algorithm. Let me denote the number 1111...1 repeated n times by 1_n. Then

1_100 = 10^40 * 1_60 + 1_40,

since multiplying 1_60 by 10^40 gives you the number with digits that are 60 1's followed by 40 0's, and then adding 1_40 just changes all of those 0's to 1's giving you 1_100. Notice that 1_40 < 1_60, so this is indeed the first step of the Euclidean algorithm. Then

1_60 = 1_40 * 10^20 + 1_20,

by similar reasoning. Finally,

1_40 = 1_20 * 10^20 + 1_20 = 1_20 * (10^20 + 1) + 0

i.e., 1_40 is divisible by 1_20. Thus, the Euclidean Algorithm is finished, so the HCF is 1_20. We can even give the factorization of 1_100 and 1_60 with 1_20 as a factor:

1_100 = 1_20*(10^80 + 10^60 + 10^40 + 10^20 + 1) and
1_60 = 1_20*(10^40 + 10^20 + 1).

In summary, the answer is (c).

Answer 3

Unfortunately, the previous writer is incorrect; at the very least, 11 is a factor of both numbers. (11 will be a factor of any number composed entirely of an even number of "1" digits.)

We can use Euclid's algorithm for this one. If you've never used it, the idea is this: if I have two numbers a and b, with a > b, then their gcd is the same as the gcd of b and (a mod b). ("a mod b" is the integer remainder when I divide a by b.) But if (a mod b) is zero, then b is a divisor of a.

As a simple example, to find the gcd of 100 and 80, I would divide 100 by 80, which gives a remainder of 20; now I divide 80 by 20, which has a zero remainder, so 20 is the gcd.

The nice thing in your case is that the a mod b values are easy to determine: they're made entirely of 1's.

When we divide 1111...11 (one hundred digits) by 1111..11 (sixty digits), we get 10^40 with a remainder of 1111..11 (forty digits).

Next we divide 1111..11 (sixty digits) by 1111..11 (forty digits), which gives us 10^20 with a remainder of 1111..11 (twenty digits), which gives us 1000..001 (nineteen zeroes), with no remainder, so the gcd must be 1111..11 (twenty digits) -- that's answer c.

Hope that was clear!