# [SOLVED] Problem from a section on Bezout's Identity

• Feb 18th 2010, 05:53 PM
Zennie
[SOLVED] Problem from a section on Bezout's Identity
Find all solutions: 561x + 909y = 81

Not just looking for answers, I don't understand the procedure. Any help is appreciated.
• Feb 18th 2010, 07:27 PM
tonio
Quote:

Originally Posted by Zennie
Find all solutions: 561x + 909y = 81

Not just looking for answers, I don't understand the procedure. Any help is appreciated.

Since $(561,909)=3$ and $3\mid 81$ , there exists a solution in integers to the given equation :

Lemma: If $(m,n)=d \,\,\,and\,\,\,d\mid b\,,\,\,say\,\,\,b=kd$ then, after writing $d=ma+nb\,,\,\,a,b\in\mathbb{Z}$ ,we get that
$m(ka)+n(kb)=kd=b$ , and $mx+ny=b$ has an integer solution.

This lemma is in fact an iff lemma.

Tonio