Expert: Sherry Wallin - 11/12/2009

Question
suppose that a and p are natural numbers and that p is prime. are there values of a and p where gcd(a,p) = 100?

thanks!

Answer
What does it mean to be the greatest common divisor? It means what is the smallest divisor that divides both numbers. For example the gcd of 12 and 20 is 4 but both 12 and 20 are composite numbers so let's look at a small prime number and a composite number, say 2 and 8, what is their gcd? yep 2. Let's try another but this time let's choose a slightly larger prime and a smaller composite like 19 and 10. What is their gcd? exactly 1. How about 50 and 89? It should be clear now that the composite number needs to be larger than the prime number and that the prime number needs to divide the composite number, i.e., that the composite is a multiple of the prime number. So is there some number that is prime that has a factor of 100? The gcd has to divide both a and p. Think, what can divide a prime? Just 1 and itself. 100 will never divide any prime because it is not prime.

Math Prof