Browse · MATH
Printjmc
number theory intermediate
Problem
For how many integers between 1 and 100 is the greatest common divisor of 15 and equal to 3?
Solution
For the greatest common divisor of 15 and to be equal to 3, must be divisible by 3 but not divisible by 5. In other words, is divisible by 3, but not by 15.
The greatest multiple of 3 that is less than or equal to 100 is 99, so there are multiples of 3 from 1 to 100. We must subtract from this the number of multiples of 15 from 1 to 100.
The greatest multiple of 15 that is less than or equal to 100 is 90, so there are multiples of 15 from 1 to 100. Therefore, there are numbers from 1 to 100 that are multiples of 3, but not 15.
The greatest multiple of 3 that is less than or equal to 100 is 99, so there are multiples of 3 from 1 to 100. We must subtract from this the number of multiples of 15 from 1 to 100.
The greatest multiple of 15 that is less than or equal to 100 is 90, so there are multiples of 15 from 1 to 100. Therefore, there are numbers from 1 to 100 that are multiples of 3, but not 15.
Final answer
27