# Prove the following statement about prime and congruence

Prove that:

$$\exists b \in \mathbb{N}, b < n \land ab \equiv 1 \textrm{ (mod n)} \to p(a,n)$$

Let $p(a,n)$ - $a$ and $n$ are relatively prime (gcd = 1)

I must prove that there exists a number b, which is less than n, and that ab is congruent to 1 mod n, implies that a and n gcd = 1

• Do you know the Bezout identity for the gcd? – Bill Dubuque Dec 11 '16 at 22:52

The number $a$ has inverse when $ab \equiv 1 \pmod n \iff \gcd(a,n)=1$
$gcd(a,n)=1 \land a^{\varphi(n)} \equiv 1 \pmod n \Rightarrow a^{\varphi(n)-1} \equiv a^{-1} \pmod n \Rightarrow a^{\varphi(n)-1} \equiv b \pmod n$
Then $b$=$a^{-1}$ and $aa^{-1} \equiv ab \equiv 1 \pmod n$