Online Course Discussion Forum

MC III Number Theory 1.10 (f)

 
 
Picture of Alan Ding
MC III Number Theory 1.10 (f)
by Alan Ding - Thursday, 14 March 2024, 8:46 PM
 

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!


 
Picture of Dr. Kevin Wang
Re: MC III Number Theory 1.10 (f)
by Dr. Kevin Wang - Friday, 15 March 2024, 1:37 AM
 

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