Solve $391x + 253y = 2760$ integer $x, y$

Question

Solve $391x + 253y = 2760$ integer $x, y$

I took some mods:

$138x \equiv 230 \pmod{253}$ this means $3x \equiv 5 \pmod{11} \implies x \equiv 9 \pmod{11}$

Thus $ \implies x = 9 + 11k$.

So, $253y = 2760 - 391*9 - 4301k \implies y = \frac{-759 - 4301k}{253} = -3 - 17k$

Thus the solution is $(9 + 11k, -3 - 17k)$ for some integer $k$?

Answer 1

First ensure solvability: $\,23=\gcd(319,253)\mid 2760\,$ is true, so cancelling $\,23\,$ it reduces to $$\,17x+11y\, =\, 120$$ Thus $ $ mod $17\!:\ {-}6y\equiv 120,\,$ so $\,y\equiv -20\equiv -3,\,$ so $\,\color{#c00}{y=-3+17k}$

Thus $\,x = (120\!-\!11\color{#c00}y)/11$ $= (120\!-\!11(\color{#c00}{-3\!+\!17k}))/17\, =\, 9-11k$

Answer 2

You can use the extended Euclidean algorithm to find that $$ 2\cdot 391 - 3\cdot 253 = 23.$$ Since $\frac{2760}{23}=120$, it isn't difficult to find a solution now.

---

Note that $ax+ by =n$ has a solution for $(x,y)$ if and only if $n$ is divisible by the greatest common divisor of $x$ and $y$.

Answer 3

Divide both sides by $23$ we have: $17x + 11y = 120 \implies y = \dfrac{120-17x}{11}= \dfrac{(110-11x)+(10-6x)}{11}= 10-x + \dfrac{10-6x}{11}$. Thus $11 \mid (10-6x)\implies 10-6x = 11k \implies x = \dfrac{10-11k}{6}= 2-2k + \dfrac{k-2}{6}\implies 6 \mid (k-2) \implies k = 6n+2, n \in \mathbb{Z}\implies x = 2- 2(6n+2) + n = -11n - 2\implies y = 10 - (-11n-2)+ \dfrac{10+6(11n+2)}{11}=17n+14 \implies (x,y) = (-11n-2, 17n+14), n \in \mathbb{Z}$