1

Prove that for any integer value of $D$, the equation $27x + 14y = D$ has integer solutions for $x$ and $y$.

amWhy
  • 209,954
Yolo
  • 25
  • How about the special case where $D=1$? – Angina Seng Dec 18 '18 at 07:22
  • Can I write assume D=1? – Yolo Dec 18 '18 at 07:24
  • " Can I write assume D=1" No. But you can find values of $x,y$ where $27x + 14y = 1$. – fleablood Dec 18 '18 at 07:28
  • @LordSharktheUnknown: what's so special about $D=1$ ? –  Dec 18 '18 at 07:29
  • @YvesDaoust: Follows from Euclidean algorithm since $\gcd(27,14)=1$. – Yadati Kiran Dec 18 '18 at 07:31
  • @YadatiKiran: I know but how can the OP know ? –  Dec 18 '18 at 07:32
  • 1
    @YvesDaoust: That's true. The tags don't seem to suggest anything with regard to elementary number theory. – Yadati Kiran Dec 18 '18 at 07:34
  • 2
    But if the OP can solve $27x + 14y = 1$ then the OP might, if clever enough, be able to apply it to solve $27x + 14y = D$. Don't think Lord shark the Unknown is required to spell it out. I think the OP can be expected to think it through. – fleablood Dec 18 '18 at 07:39
  • 1
    I'll try my best to figure out why everyone here is loving 1 so much, thanks for helping – Yolo Dec 18 '18 at 07:40
  • It might actually be worth noting and it might make it easier to notice that not only doe $27x + 14y = D$ have one solution. It actually has infinitely many solutions. It might be barking up a wrong tree to worry about what* the solution is for a specific solution. – fleablood Dec 18 '18 at 07:41
  • 1
    Well, I love one because $1 + 1 =2$ and $2 + 1 = 3$ and $3 + 1 = 4$. And $513*1 = 513$. $1$ is a pretty danged wonderful number cause it gets you places. – fleablood Dec 18 '18 at 07:42
  • Okay, so a kind soul here tagged diophantine equations that led me to whole new theorem which says if gcd(a,b) = c and if c divides D then equation has many integer solutions – Yolo Dec 18 '18 at 07:59
  • 1
    gcd(27,14) = 1 and any number is divisible by 1 therefore any value of D is has integer solutions, thanks y'all – Yolo Dec 18 '18 at 08:01

5 Answers5

9

If you can find $27x_0 + 14y_0 = 1$ then can find $27(D*x_0) + 14(D*y_0) = D$.

fleablood
  • 124,253
5

I'm by no means a math expert, but it seems to me that if you can solve for D=1, (x = -1, y = 2), then multiplying the entire equation by any integer, results in an integer solution for the general equation. I don't know how to put this into mathematical proof terms, but basically because there is a solution where D = 1, then multiplying the entire equation by some arbitrary integer c means that for any integer D, there is a solution, because you can multiply both x and y by the same number, and get a solution.

Maybe someone else can give a more formal explanation of what I'm trying to say.

CodeMonkey
  • 151
  • " then multiplying the entire equation by any integer, results in an integer solution for the general equation. " BINGO! – fleablood Dec 18 '18 at 21:38
4

$$27x+14y=D(28-27)$$

$\iff27(x+D)=14(2D-y)$

$\dfrac{14(2D-y)}{27}=x+D$ which is an integer

$\implies27|14(2D-y)\implies27|(2D-y)$ as $(14,27)=1$

$\dfrac{2D-y}{27}=c$(say) where $c$ is an arbitrary integer

$\implies y=?$

$\implies x=?$

lab bhattacharjee
  • 274,582
3

$$27x + 14y = D$$

The first step is to find one solution to $27x + 14y=1$

An "obvious" solution is $(x,y)=(-1,2)$.

Assuming you want to have a general method for finding solutions to such problems...

Start with \begin{array}{c} 27 = 27(1) + 14(0) \\ 14 = 27(0)+14(1) \end{array}

The idea is to manipulate "things" so that the number on the left becomes a $1$.

For example, $13 = 27 - 14 = 27(1-0) + 14(0-1)= 27(1) + 14(^-1)$.

We end up with the list

\begin{array}{rcl} 27 &= &27(1) + 14(0) \\ 14 &= &27(0)+14(1) \\ 13 &= &27(1)+14(^-1) \end{array}

Next we see that $1=14 - 13 = 27(0-1)+14(1-(^-1))=27(^-1)+14(2)$. So the list looks like

\begin{array}{rcl} 27 &= &27(1) + 14(0) \\ 14 &= &27(0)+14(1) \\ 13 &= &27(1)+14(^-1) \\ 1 &= &27(^-1)+14(2) \end{array}

Next we find a solution to $27x + 14y=D$

Since $27(^-1)+14(2)=1$, then $27(-D)+14(2D)= D$

Finally, we solve $27x + 14y=D$

Suppose that $27x + 14y=D$ for some $x$ and $y$. Then \begin{align} 27x + 14y=D &= 27(-D)+14(2D)= D \\ 27(x+D) &= 14(2D-y) \\ \end{align}

Since $27 \mid 27(x+D)$, then $27 \mid 14(2D-y)$.

Since $\gcd(27,14)=1$, then $27 \mid 2D-y$.

Hence, for some integer, $t$

\begin{align} 2D - y &= 27t \\ y &= 2D-27t \end{align}

Next, we solve for $x$

\begin{align} 27x + 14y &= D \\ 27x + 14(2D-27t) &= D \\ 27x + 28D - 14(27)t &= D \\ 27x &= 14(27)t - 27D \\ x &= 14t - D \end{align}

So the general solution is

$$(x,y) = (14t-D, 2D-27t)$$

for all integers, $t$.

Steven Alexis Gregory
  • 26,769
0

I see you have already some interesting answers and I will try another way to explain.

Let us make prime number factorization of numbers $27$ and $14$:

$$27 = 2^0\times 3^3\times 7^0\\14=2^1\times3^0\times 7^1$$

They don't have any non-zero exponent for the same prime base. This means $27$ and $14$ are relatively prime. If they were not relative prime, they would have some common factor $K>1$ and we could write $$K(ax+by)=D$$ But since any number $D$ is not divisible by any given common factor $K>1$, we are sure to be able to hit it.

An example if we did not have relative prime numbers is $$27x+15y=D \Leftrightarrow 3(9x+5y)=D$$ Which we can see that it could only be sure to fit if $D$ was divisible by $3$.

mathreadler
  • 25,824