Online Course Discussion Forum
MC-IIB Number Theory 6.21, 6.22
How would I prove these two problems? I'm stuck on both of them...
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$.
For 6.21, would it be enough to just say that since a and m have a gcd greater than 1, mq+r must be a times some number, so r can't be 1? I'm still kind of stuck for 6.22...it makes intuitive sense but I still don't know how to use the division algorithm...
For 6.21, one good thing to think about is the other information we're given. We also know that gcd(a, m) > 1 (so really we know that gcd(a, m) cannot be 1). If r=1 could you show that gcd(a, m) = 1?
For 6.22, let's look at an example as a hint. Consider powers of 3 (mod 11). You can double check that 3^5 = 1 (mod 11) (and that 5 is the smallest such power). Note since 3^5 = 1 (mod 11), we automatically know 3^10 = (3^5)^2 = 1^2 = 1 (mod 11). What about something like 3^12? Well since we know 3^10 = 1 (mod 11), then 3^12 = 3^2 = 9 (mod 11), which is not 1 (mod 11). Similar reasoning is happening in 6.22.
For 6.21, if a^k=am+r=1 (mod m), then r must equal 1. A number times some integer x plus one will always generate a number that's relatively prime, but how would I prove this?
You're circling around the right ideas I think for 6.21. Going back to Dr. Wang's $a^k = mq + r$ doesn't that mean that $a^k - mq = r$. If $\text{gcd}(a,m) > 1$, couldn't we factor this out of the left-hand side so that $r$ is actually a multiple of $\text{gcd}(a,m)$?
Social networks