# If $\gcd(a,b)=1$, then there exists integers $x$ and $y$ such that $xa + yb = 1$

Did not find this from this website...

If $$\gcd(a,b)=1,$$ then there exists integers $$x$$ and $$y$$ such that $$xa+yb=1.$$

Now, the tip is to use particular corollary, that states:

The class $$[m]_{n}$$ generates $$\mathbb{Z}/n\mathbb{Z}\Leftrightarrow \gcd(m,n)=1.$$

I am totally lost with the corollary.

Let's assume that $$\gcd(m,n)=1$$. Then, $$[m]_{n}$$ generates $$\mathbb{Z}/n\mathbb{Z}$$.

OK! Then what?

There is also follow up, where I have to prove the converse. I am familiar with Bezout's lemma.

• Are you trying to prove that $gcd(a,b)=1$ implies that you can find $x,y$ such that $xa+yb=1$ using the corollary? Jul 29 '15 at 0:45
• This is a particular case of Bézout's identity which you can read here en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Jul 29 '15 at 0:45
• Yes I am, Grumpy.
– Zzz
Jul 29 '15 at 0:46

Let $a$ and $b$ be coprime. Then $[a]_b$ generates $\mathbb Z/b\mathbb Z$. So there is some $x$ such that $x[a]_b=[1]_b$. By definition, this means there exists a $y$ such that $xa-1=yb$, as desired.