Common Description:
Questions (13) and (14) are based on the following information.
Let be a prime and be a natural number such that
Suppose . Show that the numbers leave distinct remainders upon division by .
none
Step-by-Step Solution
Insight: "Distinct remainders mod " means pairwise non-congruent. Assume each of the three possible collisions and derive contradictions from with .
Exam route: Three pairs to check: (i) , contradicts . (ii) or ; gives (impossible), already ruled out. (iii) ; ruled out, gives (impossible). All collisions ruled out, so leave distinct remainders.
Learning route: This is a modular distinctness proof by contradiction, recognisable from "show that ... leave distinct remainders" combined with a polynomial divisibility condition.
Step 1: "Distinct remainders mod " means no two of are congruent mod . There are pairs to check: , , and .
Step 2: Assume . Substitute into : get , so , meaning . But , contradiction.
Step 3: Assume . Factor: . Since is prime, or . If , then , so , impossible. If , already ruled out in Step 2.
Step 4: Assume . Then , so or . The case is ruled out. If , substitute into : get , impossible.
Step 5: Since all three possible collisions lead to contradictions, must leave distinct remainders modulo .