2009 Indonesia MO Problems/Problem 1
Contents
[hide]Problem
Find all positive integers such that is divisible by .
Solution 1
First, if , then , so is relatively prime to 7.
Since is relatively prime to 7, by Euler's Totient Theorem, , so . This means if is divisible by 7.
However, testing out all the residues from 1 to 6 reveals that is congruent to 1 or 6 modulo 7, so there are no positive integers such that is divisible by 7.
Solution 2
First, we let so that the given equation becomes: .
By easily checking each of the 7 possible values of we find that only satisfy the equation above. But we can also easily check that there's no such that . Therefore no integer can satisfy our equation.
~NounZero
See Also
2009 Indonesia MO (Problems) | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 | Followed by Problem 2 |
All Indonesia MO Problems and Solutions |