2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Jul 29 '15 at 0:45
  • 1
    $\begingroup$ This is a particular case of Bézout's identity which you can read here en.wikipedia.org/wiki/B%C3%A9zout%27s_identity $\endgroup$
    – Mercy King
    Jul 29 '15 at 0:45
  • $\begingroup$ Yes I am, Grumpy. $\endgroup$
    – Zzz
    Jul 29 '15 at 0:46
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.