Online Course Discussion Forum

Questions on number theory

 
 
Picture of Kepha Sher
Questions on number theory
by Kepha Sher - Sunday, October 3, 2021, 3:36 PM
 

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?


 
Picture of John Lensmire
Re: Questions on number theory
by John Lensmire - Monday, October 4, 2021, 8:32 PM
 

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

Picture of Kepha Sher
Re: Questions on number theory
by Kepha Sher - Tuesday, October 5, 2021, 6:31 PM
 

Thanks Mr. Lensmire!