Online Course Discussion Forum

MC III Number Theory 1.10 (f)

 
 
DingAlan的头像
MC III Number Theory 1.10 (f)
DingAlan - 2024年03月14日 Thursday 20:46
 

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!


 
WangDr. Kevin的头像
Re: MC III Number Theory 1.10 (f)
WangDr. Kevin - 2024年03月15日 Friday 01:37
 

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}$.