# Thread: 76x+176y=276

1. ## 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)}$

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