Could you please help me to prove the following questions:
Q1) Consider $ax ≡ c \pmod m$ (call it **), if $\gcd(a,m)=1$ then ** has a unique solution modulo $m$ i.e.
i) ** has a solution $x_0$
ii) Any solution $x$ of ** satisfies $x ≡ x_0 \pmod m$
Q2) Consider again ** and suppose $\gcd(a,m) = d ≥ 1$, we know that ** has exactly $d$ incongruent solutions: $x_0, x_1..., x_{d-1}$. By reducing them mod $m$, we can obtain exactly $d$ incongruent solutions: $0 ≤ x_0,...,x_{d-1} ≤ m-1$
Thanks in advance,
Amadeus
Answer
For i), there are many proofs. It all depends on what prior machinery you have.
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}$.
No comments:
Post a Comment