Question

If$\left(a,n\right)=1$ , prove that there is an integer $b$such that$ab\equiv 1\left(modn\right)$

Short answer

It is proved that$ab\equiv 1\left(modn\right)$ for any integer $b$.

Step-by-step solution

Consider the given condition

It is given that$\left(a,n\right)=1$ ;this implies that there exists an integer$x$ and$y$ such that $ax+ny=1$.

Rewrite the equation$ax+ny=1$ asfollows:

$ax-1=-ny$

Prove that ab≡1 mod n for any integer  b

By definition of divisibility, we can say that$\overline{)n}\left(ax-1\right)$ .

Then apply congruency definition, we have

$ax-1\equiv 0\left(modn\right)$or $ax\equiv 1\left(modn\right)$, where$x$ is an integer.

Hence, it is proved that$ab\equiv 1\left(modn\right)$ for any integer$b$ .