Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

How many integers are there such that and is a single-digit number?
Solution
If is any integer, then is one of the positive divisors of : We note that the numbers on this list with more than one digit are all multiples of , with the exception of . Thus, has a single-digit with if and only if is not a multiple of either or . Thus, we just need to count integers between and which are not multiples of or of .

There are integers such that . These include nine multiples of () and two more multiples of ( and ; we don't count because we already counted it). So, that leaves integers whose greatest common divisor with has a single digit.
Final answer
88