Skip to main content
OlympiadHQ

Browse · harp

Print

smc

number theory senior

Problem

For how many integers between and is the improper fraction in lowest terms?
(A)
(B)
(C)
(D)
Solution
What we want to know is for how many is We start by setting for some arbitrary . This shows that evenly divides . Next we want to see under which conditions also divides . We know from the previous statement that and thus Next we simply add to get However, we also want which leads to from the previous statement. From that statement, we get that divides evenly. Since is prime and we're looking for a GCD greater than 1, must be . Going back to our original statement, we can set for some positive integer x, and Finally, we must find the largest such that This is a simple linear inequality for which the answer is , or .
Final answer
B