Question

Consider the extremely large integers x = 2X3X5X7X11X13X17X19X23X29 and y = 29X31X37X41X43X47X53X59X61X67. What is the greatest common divisor of x and y?

Answer 1

I hand out medals!

Answer 2

Do you know about prime numbers?

Answer 3

Every whole number can be written as a product of prime numbers (in one way only), e.g. take 30=2x3x5.

The divisors of 30 are these factors 2, 3, 5 and products of them, so 2x3=6 is also a divisor of 30, as is 2x5.

If you compare this number with 40=2x2x2x5, some divisors of 30 and 40 are the same (common). There is only one greatest common divisor.

Once you have got the number as product of prime numbers, this greatest common divisor can easily be found.

The GCD of 30 and 40 is therefore 2x5=10. You cannot make a larger combination of prime factors that is also a divisor of both 30 and 40.

Answer 4

In the same way you can compare the divisors of your x and y to get the GCD of them.

Answer 5

You are lucky: every factor of x and of y only occurs once, so constructing the GCD will be relatively easy.

Answer 6

*

Answer 7

The GCD of these two numbers can be read without any computations.

Answer 8

The only common prime factor of x and y is 29. So what can you conclude?

Answer 9

GCD(x,y)=29

Answer 10

Thank you so much!

Answer 11

Can you help me with another problem?

Answer 12

The director of a marching band asks the band members to line up in rows of four, but one is left over. Then she tries to line them up in rows of six, but three are left over. Finally, she tries to line them up in rows of seven, but four are left over.

The band has fewer than 100 members.

How many members are there?