Find all integers for which is divisible by 19.
Solution
First note that implies . Assume now that , i.e. . Because we then have
Because 19 is a prime number, the congruence has exactly two solutions, namely . This is so because can only be divisible by the prime number 19 if one of the two factors is so. This shows that iff .
To find all such we create the following table, in which we first calculated to keep the numbers small.
| n (mod 19) | 0 | -1 | ±2 | ±3 | ±4 | ±5 | ±6 | ±7 | ±8 | ±9 |
|------------|---|----|----|----|----|----|----|----|----|----|
| (mod 19) | 0 | 1 | 4 | 9 | -3 | 6 | -2 | -8 | 7 | 5 |
| (mod 19) | 0 | -1 | ±8 | ±8 | ±7 | ∓8 | ±7 | ±1 | ∓1 | ±7 |
This shows that is divisible by 19 if and only if is congruent to 7, 8, 11, 12 or 18 (mod 19).
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.