3
$\begingroup$

I'm having troubles finding two numbers a,b such that $ 288a+177b=3=gcd(177,288) (1) $

I've been writing the equations of the Euclids algorithm one over another many times to get any pair that verify (1). But, I don't get this yet. I'm trying to solve $ 288x + 177y = 69 $ I understand very well the theorem. But I really, really need help finding the particular solution. If someone can explain me any method, or give me an advice to find a pair (a,b), I would really appreciate it. Thanks for reading,

Greetings!

$\endgroup$
4
$\begingroup$

This is how I do it in my notebook when I have to:

You first have to use the euclidean algorithm to find the greatest common divisor:

$288=(1)177+111$

$177=(1)111+66$

$111=(1)66+45$

$66=(1)45+21$

$45=(2)21+3$

$21=(7)3$ Hence the GCD is $3$. the next step is to pass all of the equations except the last so that the small number is alone:

$111=288-(1)177$

$66=177-(1)111$

$45=111-(1)66$

$21=66-1(45)$

$3=45-2(21)$.

Once I have this I start with the equation $3=45-2(21)$ and I go one by one substituting the smallest factor with the adequate equation and then simplifying:

$3=45-2(21)$

$3=45-2(66-(1)45)=3(45)-2(66)=$

$3(111-(1)66)-2(66)=3(111)-5(66)=$

$3(111)-5(177-111)=8(111)-5(177)=$

$8(288-177)-5(177)=8(288)-13(177)$

$\endgroup$
1
$\begingroup$

Suppose $288 a_1 + 177 b_1 = g$ where $\gcd(288, 177)$. The first step in Euclid's algorithm says: you take $288 = 177 + 111$, and $\gcd(288,177) = \gcd(111, 177)$. Corresponding to this, $288 a_1 + 177 b_1 = 111 a_1 + 177 (a_1 + b_1)$, so $111 a_2 + 177 b_2 = \gcd(111,177)$ where $b_2 = a_1 + b_1$. Each step of Euclid's algorithm gives you an equation in the $a$'s and $b$'s. Keep track of these equations. At the end, you'll have one that's easy to solve, and then you work backwards to get $a_1$ and $b_1$.

$\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.