integer proof problem

N

noblegas

New member
Joined
Jan 8, 2015
Messages
5
Prove that there do not exist integers x and y such that 2*x + 4*y = 7.

Proof:

I think I would start the proof by showing that 7 can't be factor out into numbers that belonged to the shared factors of 2 and 4. Or could I possible graph the expression. I have no idea how to start this proof
 
noblegas said:
Prove that there do not exist integers x and y such that 2*x + 4*y = 7.

Proof:

I think I would start the proof by showing that 7 can't be factor out into numbers that belonged to the shared factors of 2 and 4. Or could I possible graph the expression. I have no idea how to start this proof
Click to expand...
Although the easiest proof is that given by pka [one even, other odd] and other proofs would revolve around that, a general solution is given using Bézout's lemma which says in part that, for any positive integers a and b, any integer solutions to
a x + b y = d
implies d is a multiple of the greatest common divisor of a and b.

So, in this particular example, if such x and y existed then there would have to be an integer n such that 7 = 2n.
 
But "Bezoit's lemma" is just and extension of pka's idea: if ax+ by= c and n is a divisor of both a and b then a= nm, b= np for some integers m and p so ax+by= n(mx+ py)= c. Since n is a factor of left, then it must be factor of the right.

In particular, 2x+ 4y= 2(x+ 2y) has 2 as a factor. It can't be equal to 7 because 2 is not a factor of 7.
 
You must log in or register to reply here.
Top