Skip to main content
OlympiadHQ

Browse · MathNet

Print

Austria 2010

Austria 2010 number theory

Problem

Let Prove that for every integer with , there is no non-negative integer such that is divisible by .
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

Techniques

Fermat / Euler / Wilson theoremsMultiplicative orderPolynomial operations