2003 Pan African MO Problems/Problem 5
Problem
Find all positive integers such that divides .
Solution
In order for an integer to be divisible by , the integer must be divisible by both and .
For divisibility by 3, note that if is even and if is odd. Since is even for , we must have for all values of . Therefore, must be an even number.
For divisibility by 7, because , we must have . Additionally, by trying small values of , we find that .
Thus, we suspect that if is even and that if is odd. To prove this, we can use induction. For the base case, we know that and that . For the inductive step, assume that . By using properties of exponents and modular arithmetic, we have . Additionally, . The inductive step holds, so if is even and that if is odd.
Because we know that must be even, . Therefore, we must have , so . In summary, the integers that satisfy the original conditions are in the form .
See Also
2003 Pan African MO (Problems) | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All Pan African MO Problems and Solutions |