Prove that for every n ∈ Z, there exist a, b ∈ Z such that $n = 5a + 2b$.

Question

This is a question the prof asked in my university math proofs course. I've tried this for a bit over an hour and I am stuck.

The method I personally chose was proof by cases:

Case 1: n is even:

Thus $n = 2k$ for some k ∈ Z. So $n = 2k = 5a + 2b$

Here I can choose $a=0$, thus $n = 2k = 2b$ Therefore, if n is even there always exists some a,b∈ Z such that $n = 5a + 2b$ and case 1 is true.

Case 2: n is odd:

Thus $n = 2k+1$ for some k ∈ Z. So $n = 2k+1 = 5a + 2b$

This is where I'm stuck, I cant seem to show that the case is always true for when n is odd.

If you could give me a hint in the right direction or complete my method of proof by cases that would be great, or if you had another method of proving it that would be helpful too.

Thanks, John

Answer 1

Doing cases is inefficient and I hope you play around a bit to see why but:

If $n = 2k + 1$ is odd.

Then $n = 2k + 1 = 2k + 5 - 2 = 2(k-2) + 5$ so let $a= 1$ and $b=k-2$.

=====

But it might be nicer to note:

$1 = (1)*5 + (-2)*2$.

So $n = n*1 = n*5 + (-2n)*2$. SO let $a = n$ and $b = -2n$.

I'll let you play around and try to figure out why I consider that "nicer".

Answer 2

You have $5-(2)(2)=1$, thus $n=5n-2(2n)$ take $a=n, b=-2n$.

Answer 3

a=1 will work for all odd numbers. :)

Answer 4

Bezout's identity says that there exist integers $x,y$ such that $2x+5y=1$, since $(2,5)=1$. Then just multiply by $n$.

Answer 5

Let me do a general case. Suppose we have integers $a,b$ such that $(a,b)=1$. Let's prove that the integer equation $ax+by=n$ has solution for $x,y$ regardless of any integer $n$ we care to pick.

Proof: Bezout's identity asserts that there are integers $x_0$, $y_0$ such that $ax_0+by_0=1$. Therefore $n(ax_0+by_0)=n$, which is to say, the choice $x=nx_0$ and $y=ny_0$ works.

In general, if we have $(a,b)=d$, then any multiple of $d$ can be expressed in the form $ax+by$ by an identical argument as above, but starting with a slightly more general version of Bezout's identity. In fact, it's also true that in this case, we always have infinitely many pairs $(x,y)$ that satisfy the equation. We even have a parametrisation! Can you find these?

Answer 6

Every odd number differs from other odd numbers by some multiple of $2$. So if $5a$ is odd (such as when $a=1$, as suggested in another answer), there will be some value of $b$ such that $5a+2b$ will be equal to any odd number: $(2k+1)-5=(2k-4)=2(k-2)=2b$. Similarly, every even number differs from other even numbers by some multiple of $2$. By the same reasoning, if $5a$ is even (such as when $a=2$), there will be some value of $b$ such that $5a+2b$ will be equal to any even number: $2k-10=2(k-5)=2b$. Having shown that every odd and every even number can be represented as $5a+2b$, the point is proved.