Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

What is the unique three-digit positive integer satisfying
Solution
We can start by multiplying both sides of the congruence by and evaluating both sides modulo :

Why multiply by ? Well, as the computations above show, the result is to produce a congruence equivalent to the original congruence, but with a much smaller coefficient for .

From here, we could repeat the same strategy a couple more times; for example, multiplying both sides by would give on the left side, reducing the coefficient of further. One more such step would reduce the coefficient of to , giving us the solution.

However, there is an alternative way of solving . We note that we can rewrite this congruence as (since ). Then is a multiple of : specifically, , so multiplying both sides by gives This is the solution set to the original congruence. The unique three-digit positive solution is
Final answer
668