We use the Euclidean algorithm for finding the GCD.
To find the GCD of a and b, where a < b
1. divide a into b, getting remainder r1
2. divide r1 into a, getting remainder r2
3. divide r2 into r1, getting remainder r3
4. divide r3 into r2, getting remainder r4
....
eventually we will get a zero remainder, and the
divisor used which gave that 0 remainder is the GCD.
We begin the algorithm by dividing 1111 into n
We can rewrite n this way:
All those terms are divisible by 1111 except the last one,
22, and therefore 22 will be the remainder when n is divided
by 1111. Maybe this isn't obvious, so I'll explain:
1111 will divide evenly into any integer containing
all 2's if and only if it has a multiple of 4 digits.
But 2002 is not a multiple of 4, it's 2 more than a
multiple of 4, since 2002 mod 4 = 2. So at the end
of the division we will bring down those last two 2's
and so the remainder will be 22. You can see that
by observing the division, skipping a space between
each block of 4 2's
2 0002 0002 0002 00
1111)2222 2222 2222···2222 22
2222
2222
2222
2222
2222
···
2222
2222
22
Now we can complete the Euclidean algorithm:
50
22)1111
110
11
2
11)22
22
0
The divisor which gives us a 0 remainder
is the GCD, and that is 11.
So the greatest common divisor of 1111 and n is 11.
Edwin
