Find all pairs of positive integers such that:
* is the smallest positive integer that is not a factor of , and;
* is a factor of .
Solution
A complete list of solutions is
| 1 | 2 | 4 | 13 | 14 | 28 | |
|---|---|---|---|---|---|---|
| 2 | 3 | 3 | 2 | 3 | 3 | |
| 13 | 28 | 28 | 13 | 28 | 28 |
Solution:
Solution 1. Any factor of is a factor of . Hence, cannot be a factor of . Hence, , the smallest non-factor of , can only be or , as non-factors of and above cannot be the smallest non-factor. If , must be an odd factor of , i.e. or . If , then must be an even factor of , i.e. . This gives the solutions as tabulated above.
Solution 2. Clearly as is a factor of all positive integers . The minimality of implies that is a factor of which is a factor of , so . We also have . By subtraction , so and so . Checking the factors of for possible values of gives the solutions above.
Solution 3. Trying and and trying in turn each factor of as a candidate for gives all the solutions stated. If then are factors of and in particular is multiple of , hence and as well, i.e. . But this means that would have to be a quadratic residue modulo , which is not the case.