Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory intermediate

Problem

Determine the number of positive integers less than such that the congruence has a solution in .
Solution
The given congruence has a solution if and only if is invertible modulo since the congruence implies that are inverses of each other modulo . In other words, . The only such positive less than are . So the number of possible values of is .
Final answer
4