0

I know that in general, for two integers $a$ and $b$, there exist integers $x$ and $y$ such that \begin{equation} ax+by=gcd(a,b) \end{equation} In this case, let $a=6$ and $b=15$ and let the right-hand-side equal $2$. Do there exist any $x$ and $y$ so that \begin{equation} 6x+15y=2? \end{equation} Note that $2 \ne gcd(6,15)=3$. However, this is what my question comes down to: I know that there DO exist solutions $x$ and $y$ to \begin{equation} 6x+15y=3 \end{equation} However, as far as I know, $3$ isn't the ONLY right-hand-side for which this works, is it? In other words, is the greatest common divisor the only possible right-hand-side for which this works?

Thanks!

EthanAlvaree
  • 3,412
  • 1
    The number on the R.H.S. must be divisible by the $\gcd$ not necessarily the $\gcd$ itself. –  Dec 05 '14 at 08:19
  • Take $x=1$ and $y=2$, and you will see that $36$ is a perfectly good solution for the R.H.S. which is not $3$. – Martigan Dec 05 '14 at 08:20
  • $n$ can be written as $6x+15y$ if and only if $\gcd(6,15)=3$ divides $n$ – drhab Dec 05 '14 at 08:22
  • 1
    $3(2x+5y)=2$ - I don't see how any integer value of $2x+5y$ could be multiplied by $3$ and yield $2$. In other words: $\forall{x,y}\in\mathbb{Z}:2x+5y\in\mathbb{Z}$, but $6x+15y=2\implies3(2x+5y)=2\implies2x+5y=\frac23\not\in\mathbb{Z}$. – barak manos Dec 05 '14 at 08:23

2 Answers2

1

Since $6x + 15 y = 3(2x + 5y)$, the LHS will always be divisible by $3$. Therefor, there cannot be any solution unless the RHS is also divisible by $3$.

Assume now that this is the case, i.e., consider the equation $6x + 15y = k \gcd(6,15) = 3 k$, where $k$ is some integer. As you already have noticed, there exists integers $x_0$, $y_0$ such that $6x_0 + 15y_0 = 3$. Multiplying both sides by $k$ you obtain that $6(kx_0) + 15(ky_0) = 3 k$. That is, $x = kx_0$ and $y = ky_0$ is a solution to our equation.

Raclette
  • 613
1

We want to find integer $(x,y)$ such that $6x+15y=2$. Since when $(x,y)=(0,0)$,this is not true. Since $\gcd(6,15)=3$ So given equation will be $3(2x+5y)=2$. Since term in bracket can only be an integer or zero, Hence $3(2x+5y)$ is multiple of $3$ or $0$. Since $2$ is not a multiple of $3$, so no solution with $x,y$ both integer is possible, I think you can generalize from here

drhab
  • 151,093
TheDragonReborn
  • 918
  • 1
    "integer or zero": zero is also an integer. "multiple of $3$ or $0$": $0$ is also a multiple of $3$. You are not dealing with separate cases here. It makes your proof less elegant. – drhab Dec 05 '14 at 08:34
  • I have use 0 as special case in lot of problem,old habits doesn't die ;) – TheDragonReborn Dec 05 '14 at 08:39