Online Course Discussion Forum
Questions on number theory
I learned a lot about the formulas for number theory, but I have some questions:
1. If gcd(a, m) ≠ 1, then is it guaranteed that the modular inverse of a mod m does not exist?
2. Similarly, if gcd(a, m) ≠ 1, then is it guaranteed that the extended fermat's theorem does not work?
Here's some ideas to think about a little more to explore 1. and 2.
1. It is guaranteed that the inverse doesn't exist. Suppose there is a $j$ so that $j\cdot a \equiv 1 \pmod{m}$. Note this means for some $k$ then $j\cdot a = 1 + k\cdot m$ or $j\cdot a - k\cdot m = 1$. Try to use this to show that $\gcd(a,m)$ cannot be greater than $1$.
2. Take a look at Practice Problem 6.21 in the MC II-A Number Theory book for a hint on how to show that if $\gcd(a,m) > 1$, then $a^k \not\equiv 1 \pmod{m}$ for ANY value of $k$.
Lastly, remember that neither Fermat's Little Theorem nor the extension say that $p-1$ or $\phi(m)$ are the smallest powers of a number that are $1 \pmod{m}$. They just guarantee that the value DOES work. For example, $\phi(100) = 40$, so we are guaranteed that $11^{40} \equiv 1 \pmod{100}$. In fact, however, $11^{10} \equiv 1 \pmod{100}$.
Social networks