76x+176y=276

• Jul 16th 2010, 04:46 PM
dwsmith
76x+176y=276
$\displaystyle 76x+176y=276$

$\displaystyle 76x\equiv 276 \ \mbox{(mod 176)}\Rightarrow 76x\equiv -76 \ \mbox{(mod 176)}\Rightarrow x_0=-1$

$\displaystyle 176y\equiv 276 \ \mbox{(mod 76)}\Rightarrow 24y\equiv 48 \ \mbox{(mod 76)}\Rightarrow y_0=2$

$\displaystyle x=-1+44t$

$\displaystyle y=2-19t$

However, this is wrong. Isn't the formula:

$\displaystyle x=x_0+\frac{m}{gcd(76,176)}$

$\displaystyle y=y_0-\frac{m}{gcd(76,176)}$
• Jul 16th 2010, 05:28 PM
undefined
Quote:

Originally Posted by dwsmith
$\displaystyle 76x+176y=276$

$\displaystyle 76x\equiv 276 \ \mbox{(mod 176)}\Rightarrow 76x\equiv -76 \ \mbox{(mod 176)}\Rightarrow x_0=-1$

$\displaystyle 176y\equiv 276 \ \mbox{(mod 76)}\Rightarrow 24y\equiv 48 \ \mbox{(mod 76)}\Rightarrow y_0=2$

$\displaystyle x=-1+69t$

$\displaystyle y=2-69t$

However, this is wrong. Isn't the formula:

$\displaystyle x=x_0+\frac{m}{gcd(76,176)}$

$\displaystyle y=y_0-\frac{m}{gcd(76,176)}$

It works out with

$\displaystyle x=x_0+\left(\frac{176}{gcd(76,176)}\right)t$

$\displaystyle y=y_0-\left(\frac{76}{gcd(76,176)}\right)t$