Let
Prove that for every integer with , there is no non-negative integer such that is divisible by .
, 2010
Solution
Assume that divides for some integer and some . As and is a prime number, cannot be a divisor of , so we may restrict ourselves to the case .
In this case, we can write as
Let be a prime divisor of . Then we have , which results in
This immediately implies that and are coprime.
By (1), the order of modulo , i.e., the smallest positive exponent such that , is a divisor of . As is prime, this results in .
If , we have , which results in (by the original definition of ). This implies and therefore , contradiction.
We conclude that . As always divides by Fermat's theorem, we conclude that is a multiple of . This is a contradiction to . qed
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.