Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

I have a few questions about this:

  • 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?

share|improve this question
    
    
Check this answer, especially the reference about numerical monoids... –  draks ... Feb 5 '13 at 22:25
add comment

4 Answers

up vote 4 down vote accepted

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$.

share|improve this answer
    
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
1  
@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
show 1 more comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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). $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.