The lemma in p. 231 of the book “A book of abstract algebra” by Charles C. Pinter states that if and are relatively prime, then the equation has a solution modulo . It is also stated below the lemma that if and are not relatively prime, then the equation has no solution modulo . By contraposition, the latter statement means that if the equation has a solution modulo , then and are relatively prime.
More generally, less emphasis is given on the converse of the lemma in the literature. The purpose of this post is to clarify that the equivalence holds. To start with, and are relatively prime if and only if their greatest common divisor satisfies . Along these lines, the lemma can then be stated in the following way; if and only if the equation has a solution modulo .
Proofs of the fact that means that the equation has a solution modulo are available in Pinter’s book and elsewhere in the literature, so interest is in proving the converse. It will be shown that if the equation has a solution modulo , then .
If the congruence has a solution, then it has a solution modulo , where (see for example theorem 2, p. 231, in Pinter’s book). Obviously, .
It will be shown that . Towards this end, assume that . So, it has been assumed that the congruence has a solution modulo . This means that it has a solution, therefore it has a solution modulo .
Let be the solution modulo and the solution modulo . Since is a solution of the congruence , it follows that . The congruences and lead to .
So, . Notice now that implies , hence the coset equality holds in , where . Similarly, yields in , where . It has thus been concluded that , which is a contradiction since for example , while for . Thereby, .
and give , which completes the proof.