Let , , and let with . Prove that if and are not relatively prime, then there exists an integer with such that . Deduce that there cannot exist an integer such that .
Suppose . Then we have for some , and . Moreover for some , so that, mod n, we have .
Suppose now that mod n for some . Then we have, mod n, . But then , a contradiction. So no such exists.