0
$\begingroup$

It's easy to show that relatively prime numbers have inverse mod n via the Euclidian Algorithm-How do you show that they don't necessarily have an inverse if they aren't relatively prime? I would think you would start by pulling out a common factor, then maybe showing that if that factor isn't one, you'll always have some number greater than one time an integer for any power of the number, so there wouldn't be an inverse... but I think I'm wrong.

$\endgroup$
1
$\begingroup$

$$mm'\equiv 1\pmod{n} \Leftrightarrow mm'-1 = kn \Leftrightarrow mm'-kn = 1\Leftrightarrow \gcd(m, n) = 1$$

$\endgroup$
0
$\begingroup$

Fix some n, such as 6. Take a number not coprime to $n$, then take its sequence of multiples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy