Online Course Discussion Forum
MC III Number Theory 1.10 (f)
Part (f) was not explained in class, and I don't really get the solution. Could anyone explain it in farther detail? Help is greatly appreciated!
The question asks whether the following is true: Assume $\gcd(a,m)=1$, and $k\geq 1$. If $a^k\equiv b^k\pmod{m}$ and $a^{k+1}\equiv b^{k+1}\pmod{m}$, then $a\equiv b\pmod{m}$.
This is true. To prove this, note that we are effectively doing division. In the context of modular arithmetic, dividing by $a$ means multiplying by the inverse of $a$. Since $\gcd(a,m)=1$, the inverse of $a$ modulo $m$ exists. Also $\gcd(a^k,m)$ must be $1$ as well, and the inverse of $a^k$ also exists. We are given that $a^k$ and $b^k$ are congruent modulo $m$, thus, the inverse of $b^k$ also exists and is the same as the inverse of $a^k$. Multiplying the inverse of $a^k$ (same as that of $b^k$) to both sides of $a^{k+1}\equiv b^{k+1}\pmod{m}$, then we get $a\equiv b\pmod{m}$.
Social networks