Category Archives: Number theory

Proof: a and n are relatively prime iff ax≡b(modn) has a solution modulo n

The lemma in p. 231 of the book “A book of abstract algebra” by Charles C. Pinter states that if a and n are relatively prime, then the equation ax\equiv b(\mbox{mod} n) has a solution modulo n. It is also stated below the lemma that if a and n are not relatively prime, then the equation ax\equiv b(\mbox{mod} n) has no solution modulo n. By contraposition, the latter statement means that if the equation ax\equiv b(\mbox{mod} n) has a solution modulo n, then a and n 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, a and n are relatively prime if and only if their greatest common divisor satisfies \mbox{gcd}(a, n)=1. Along these lines, the lemma can then be stated in the following way; \mbox{gcd}(a, n)=1 if and only if the equation ax\equiv b(\mbox{mod} n) has a solution modulo n.

Proofs of the fact that \mbox{gcd}(a, n)=1 means that the equation ax\equiv b(\mbox{mod} n) has a solution modulo n 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 ax\equiv b(\mbox{mod} n) has a solution modulo n, then \mbox{gcd}(a, n)=1.

If the congruence ax\equiv b(\mbox{mod} n) has a solution, then it has a solution modulo m, where m = n/\mbox{gcd}(a,n) (see for example theorem 2, p. 231, in Pinter’s book). Obviously, m\le n.

It will be shown that m = n. Towards this end, assume that m < n. So, it has been assumed that the congruence ax\equiv b(\mbox{mod} n) has a solution modulo n. This means that it has a solution, therefore it has a solution modulo m.

Let x\equiv c(\mbox{mod}m) be the solution modulo m and x\equiv r(\mbox{mod}n) the solution modulo n. Since x = c is a solution of the congruence ax\equiv b(\mbox{mod} n), it follows that c\equiv r(\mbox{mod}n). The congruences x\equiv r(\mbox{mod}n) and c\equiv r(\mbox{mod}n) lead to x\equiv c(\mbox{mod}n).

So, x\equiv c(\mbox{mod}n)\Leftrightarrow x\equiv c(\mbox{mod}m). Notice now that x\equiv c(\mbox{mod}n) implies x-c\equiv 0(\mbox{mod}n), hence the coset equality \overline{x-c}=\overline{0}_n holds in \mathbb{Z}_n, where \overline{0}_n=\{\dots,-2n,-n,0,n,2n,\dots\}. Similarly, x\equiv c(\mbox{mod}m) yields \overline{x-c}=\overline{0}_m in \mathbb{Z}_m, where \overline{0}_m=\{\dots,-2m,-m,0,m,2m,\dots\}. It has thus been concluded that \overline{0}_n=\overline{0}_m, which is a contradiction since for example m\in\overline{0}_m, while m\not\in\overline{0}_n for m<n. Thereby, m=n.

m=n and m = n/\mbox{gcd}(a,n) give \mbox{gcd}(a, n)=1, which completes the proof.