Question

Show that an inverse of $a$and $m$ where $a$ is an integers, and $m>2$ is a positive integer, does not exist if $\gcd \left(a,m\right)>1$

Short answer

An inverse of modulo m does not exist.

Step-by-step solution

Step 1

Given $a$ is an integer and $m>2$is a positive integer.

$\gcd \left(a,m\right)>1$

To proof: An inverse of $a$ modulo $m$does not exist.

Proof by contradiction

Let us assume that $b$ is the inverse of$a$ modulo$m$.

The inverse of $a$modulo $m$ is an integer $b$ for which $ab\equiv 1\left(\mathrm{mod}m\right)$

$ab\equiv 1\left(\mathrm{mod}m\right)$

$a$ is congruent to $b$modulo $m$ if $m$divides $a-b$

Notation $ab\equiv 1\left(\mathrm{mod}m\right)$

$m|ab-1$

Then there exists a constant such that

$ab-1=mc$

Step 2

Let $d=\gcd \left(a,m\right)$.By definition of the greatest common divisor$d$, divides both integers

$$\begin{gathered} d\left|a \\ d\right|m \end{gathered}$$

If $x|y$then $x|yz$for every positive integer

$$\begin{gathered} d\left|ab \\ d\right|mc \end{gathered}$$

Since $ab-1=mc$or equivalently $ab-mc=1$

$d|1$

A positive integer divides 1if the integer 1 is itself

$d=1$

We have then obtained a contradiction, because $d=\gcd \left(a,m\right)>1$ and thus our assumption that an inverse exists is false.