Online Course Discussion Forum
Math Challenge II-A Number Theory
For these fundamental proof problems, try to use the division algorithm:
For any integers $a$ and $b$, where $b > 0$, there exists a unique pair of $q$ and $r$ ($0\leq r < b$, such that $a=bq + r$.
Here $q$ is the quotient, and $r$ is the remainder.
For 6.21, we want to find out the remainder when $a^k$ is divided by $m$. According to the division algorithm, $a^k = mq + r$. From here, can you show that $r$ cannot be $1$?
For 6.22, $j$ is the smallest positive exponent to have $a^j\equiv 1\pmod{m}$. For any other $k$ where $a^k\equiv 1\pmod{m}$, we use the division algorithm on $k$ and $j$: $k = jq + r$. We want to show that $r$ must be $0$.
Social networks