Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory intermediate

Problem

The number of apples that Sophia has is a multiple of . When she sells one apple, the number of apples is a multiple of . If is a positive integer less than , how many possible values are there for ?
Solution
Let be the number of apples that Sophia originally had. Clearly for some positive integer . Additionally, . This is solvable for if and only if is invertible modulo . In other words, . The only such less than are , so there are possibilities for .
Final answer
3