# Proof help needed about Congruences

Q1) Consider ax ≡ c mod m (call it **), if gcd(a,m)=1 ⇒ ** has a unique solution module m i.e.

i) ** has a solution X0

ii) Any solution x of ** satisfies x ≡ X0 mod m

Q2) Consider again ** and suppose gcd(a,m) = d ≥ 1, we know that ** has exactly d incongruent solutions: X0, X1..., Xd-1. By reducing them mod m, we can obtain exactly d incongruent solutions: 0 ≤ X0,...,Xd-1 ≤ m-1

-

One relatively low-tech way of doing it is to consider the numbers $(a)(0), (a)(1), (a)(2), \dots, (a)(m-1)$. We will show that these are all incongruent modulo $m$.
For suppose to the contrary that $ai\equiv aj\pmod{m}$, with $0\le i\lt j\le m-1$. Then $aj-ai=a(j-i)$ is divisible by $m$. But since $\gcd(a,m)=1$, it follows that $m$ divides $j-i$. This is impossible, since $0\lt j-i\le m-1$.
We conclude that modulo $m$, the numbers $(a)(0), (a)(1),\dots, (a)(m-1)$ are congruent, in some order, to $0,1,2,3,\dots,m-1$. It follows that there is exactly one $i$ such that $ai\equiv c\pmod{m}$.
A way to prove it with more machinery is if we know that whenever $\gcd(a,m)=1$, there is a $b$ such that $ab\equiv 1\pmod{m}$. Then let $x=bc$. We conclude that $ax=a(bc)=(ab)c\equiv c\pmod{m}$. For uniqueness, suppose that $ax\equiv ay\equiv c\pmod{m}$. Multiply by $b$. We get $b(ax)\equiv (b(ay)\pmod{m}$. But since $ba\equiv 1\pmod{m}$, it follows that $x\equiv y\pmod{m}$.