# Show that every integer can be written in the form $5a + 7b$ for $a,b \in \mathbb{Z}$

Show that every integer can be written in the form $5a + 7b$ for $a,b \in \mathbb{Z}$. HINT: Find, $a_1$ and $b_1$ such that $5a_1 + 7b_1 = 1$.

• How do I gout about finding that $a_1, b_1$? I mean, is there a method I can use, or do I just have to trial and error?
• Once I've found this, how does that prove that every integer can be written in the form?

The next question says

Show that ever integer $n \geq 24$ can be written in the form $5a + 7b$ for $a,b \in \mathbb{N}$.

I think I can do this, but the question I have about this one is, if I have something in the form $ax + by$, then how do I know what integers I can write this as? Like, just taking this question as an example, how do you know that it is for all $n \geq 24$ and not any thing less than, or would this by trial and error as well?

EDIT: It took my like 2 seconds to get $a_1 = 3$ and $b_1 = -2$, but if they were bigger or more difficult numbers, would I still use trial and error or is there an actual procedure?

-
Check this answer, especially the reference about numerical monoids... – draks ... Feb 5 '13 at 22:25

In this case the numbers are small enough that the easiest way to find $a_1$ and $b_1$ is trial and error: I notice immediately that $4\cdot5$ and $3\cdot7$ differ by $1$, which gives my an $a_1$ and $b_1$ that work.

In general if $\gcd(m,n)=d$, there are integers $a$ and $b$ such that $am+bn=d$; in this problem $d=1$. If you apply the Euclidean algorithm to $m$ and $n$ to get the gcd $d$, you can then back-solve to write $d$ in the form $am+bn$; this gives you a systematic approach to finding $a_1$ and $b_1$. Here, for instance, the Euclidean algorithm gives you

\begin{align*} 7&=1\cdot5+2\\ 5&=2\cdot2+1\;, \end{align*}

so

\begin{align*} 1&=1\cdot5-2\cdot2\\ &=1\cdot5-2(1\cdot7-1\cdot5)\\ &=3\cdot5-2\cdot7\;, \end{align*}

and I can take $a_1=3,b_1=-2$, an even nicer choice than my top-of-the-head choice in the first paragraph.

The second question is easily answered by induction. If you can find solutions for $5$ consecutive numbers (e.g., $24,25,26,27$, and $28$, then there must be a solution for each integer larger than these, since each larger integer is one of these plus a multiple of $5$. This provides an alternative proof for the first problem, by the way, since you can also repeatedly subtract $5$ from these five solutions to get solutions, possibly in negative integers, for every smaller integer as well, including the negative integers. This requires another induction, this time a downward induction through the integers less than the starting five.

The general result is that for relatively prime integers $m$ and $n$, every integer greater than or equal to $(m-1)(n-1)$ can be represented as $am+bn$ for non-negative integers $a$ and $b$. (In your case $(5-1)(7-1)=24$.) Moreover, exactly half of the non-negative integers less than $(m-1)(n-1)$ can be so represented, and $(m-1)(n-1)-1$ is one that cannot. Links in this answer will give you more information on this.

Added to answer a question in the comments: The Euclidean algorithm applied to $183$ and $257$ yields

\begin{align*} 257&=1\cdot183+74\\ 183&=2\cdot74+35\\ 74&=2\cdot35=4\\ 35&=8\cdot4+3\\ 4&=1\cdot3+1\;. \end{align*}

Back-solving for $1$ in terms of $183$ and $257$:

\begin{align*} 1&=1\cdot4-1\cdot3\\ &=1\cdot4-1\cdot(1\cdot35-8\cdot4)\\ &=9\cdot4-1\cdot35\\ &=9\cdot(1\cdot74-2\cdot35)-1\cdot35\\ &=9\cdot74-19\cdot35\\ &=9\cdot74-19\cdot(1\cdot183-2\cdot74)\\ &=47\cdot74-19\cdot183\\ &=47\cdot(1\cdot257-1\cdot183)-19\cdot183\\ &=47\cdot257-66\cdot183\;. \end{align*}

And indeed $47\cdot257-66\cdot183=12079-12078=1$.

-
Ok, thank you for your answer. Is there a quick way to find say $51 + 7b = 24$ then? As I can't use Euclidean algorithm for that can I? – Kaish Feb 5 '13 at 22:19
@Kaish: You can in principle get it from the first part. You know that $3\cdot5-2\cdot7=1$, so $72\cdot5-48\cdot7=24$. Now notice that if $5a+7b=n$, then $5(a-7)+7(b+5)=n$ as well. If I add $10\cdot5$ to $-48$, I’ll get $2$, which is positive; to compensate, I must subtract $10\cdot7=70$ from $72$, again getting $2$. Thus, $2\cdot5+2\cdot7=24$. This idea works in general. However, it would have been quicker in this case just to run through $24$, $24-7$, $24-2\cdot7$, and $24-3\cdot7$ looking for a multiple of $5$. – Brian M. Scott Feb 5 '13 at 22:26
I have one more question about working out $a$ and $b$. I needed to work that for $183a + 257b = 1$. Now I did Euclids algorithm and got it so the gcd = 1, but from these numbers, how do I get $a$ and $b$? – Kaish Feb 5 '13 at 23:26
@Kaish: It’s too long for a comment; give me a few minutes to add it to my answer. – Brian M. Scott Feb 5 '13 at 23:31
@Kaish: That example is long enough that the general method should be clear. There are computationally more efficient ways to carry out the idea; you’ll find a discussion here. – Brian M. Scott Feb 5 '13 at 23:40

Trial and error would be my suggestion though it isn't that hard given that 5*3=15 and 7*2=14 for one idea of a starting point, though you could use 5*4=20 and 7*3=21 for another possibility.

The idea would be that if you can find solutions to generate 1, then to generate any other integer k, you could multiply the a and b by k to get that result. For example, 5*0+7*0=0 would be a solution for getting zero.

For the next question, the key is to notice that if you can get a set of solutions for 5 consecutive integers, then you could recycle most of that answer but increment a for all the multiple of 5s that one is away from it. For example, suppose you have {a,b},{c,d},{e,f}, {g,h}, {i,j} that are the solutions for n=24,25,26,27, and 28 respectively. Any solution for 24 could made into a solution for 29 by incrementing the value for a by 1.

-

There is a method, you can get those $a,b$ numbers by Euclidean algorithm in finding the greatest common divisor of $a$ and $b$. It goes like:

• Divide with remainder $\ 7=1\cdot 5+2$
• Continue with the smaller one and the remainder: $5 =2\cdot 2+1$

Now it ended right now with the remainder $1$ we wanted to express, so writing back, we get $$2=7-1\cdot 5 \\ 1=5-2\cdot 2=5-2\cdot (7-1\cdot 5) =3\cdot 5-2\cdot 7$$

But for these specific numbers, as $3\cdot 5=15=2\cdot 7+1$, the trial can become faster.

-
Ok thanks, but lets say that now (lets use my example), its not equal to $1$, but something else instead. Let's say $24$ as we know thats possible, how would I do that? Also, what Euler algorithm? I have a Euclidean one written down to work out gcd but no Euler? Unless I've made a mistake somewhere... – Kaish Feb 5 '13 at 21:46
You are right, Euclidean. I have added the concrete details. – Berci Feb 5 '13 at 21:48

I am not sure this has been mentioned in the other answers. Given integers $m, n$, then the numbers that can be represented in the form $m a + n b$, for $a, b$ integers, are the multiples of the gcd $(m, n)$.

It is clear that all numbers $m a + n b$ are multiples of $(m, n)$.

Conversely, let $z = (m, n) t$, with $z, t$ integers. Use Euclid's algorithm to find integers $x, y$ such that $m x + n y = (m, n)$. Now multiply by $t$ to obtain $$z = (m, n) t = m (x t) + n (y t).$$

-