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

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?
 A: 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.
A: 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.
A: 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).
$$
