Online Course Discussion Forum

Math Challenge II-A Number Theory

 
 
Picture of Dr. Kevin Wang
Re: Math Challenge II-A Number Theory
by Dr. Kevin Wang - Monday, August 26, 2024, 7:59 AM
 

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