Browse · MATH
Printjmc
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
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