This problem is about number theory in Descrete mathmatics S

This problem is about number theory in Descrete mathmatics.

Show that, when a and m are not relatively prime, the inverse of a modulo m may not exist.

Solution

Let inverse of a modulo m exist.

ie there is x so that

ax=1 mod m

ax-1=km

ax-km=1

But a and m are not relatively prime

So gcd(a,m)=g>1

so, a=pg,m=rg

Substituting gives

apg-krg=1

(ap-kr)g=1

Now ap-kr is an integer and g is an integer larger than one so the product cannot be equal to 1.

Hence we have a contradiction

So inverse of a modulo m does not exist.