Online Course Discussion Forum

Questions on number theory

 
 
SherKepha的头像
Questions on number theory
SherKepha - 2021年10月3日 Sunday 15:36
 

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?


 
LensmireJohn的头像
Re: Questions on number theory
LensmireJohn - 2021年10月4日 Monday 20:32
 

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

SherKepha的头像
Re: Questions on number theory
SherKepha - 2021年10月5日 Tuesday 18:31
 

Thanks Mr. Lensmire!