# Divisibility (gcd) 10

• December 19th 2008, 02:56 PM
Sea
Divisibility (gcd) 10
$x\in \mathbf{Z^{+}}$ and $y\in\mathbf{Z}$

$26x+14y=(26,14) \Rightarrow$ min x =?
• December 19th 2008, 05:44 PM
o_O
$26x + 14y = 2 \ \Leftrightarrow \ 13x + 7y = 1$

By inspection, we can see that a solution is given by: $x = -1, \ y = 2$

Thus, all solutions are given by: $x = -1 + \frac{14}{(26,14)}t, \ \ \ y = 2 - \frac{26}{(26,14)}t$ where $t \in \mathbb{Z}$

Since we want positive x's, we want:
\begin{aligned} x = -1 + \frac{14}{(26,14)}t & > 0 \\ -1 + 7t & > 0 \\ t & > \frac{1}{7} \approx 0.14286\end{aligned}

Thus, for all $t > \tfrac{1}{7}$, we have positive x's as our solution.