Ways to proof statement of divisor of linear combination

Question

I would like to know the ways to proof the statement if it's true: For every integer n, there exists integers s and t such as 5s + 8t = n

Answer 1

Euclidean algorithm:

5 divides into 8 once with remainder 3: 8- 5= 3.

3 divides into 5 once with remainder 2: 5- 3= 2.

Finally, 2 divides into 3 once with remainder 1: 3- 2= 1.

(The fact that we can, using the Euclidean algorithm, finally get a remainder of one depends on the fact that 8 and 5 are "relatively prime"- they have greatest common divisor 1, as gimusi said.)

Replace the "2" in that last equation with "5- 3": 3- (5- 3)= 2(3)- 5= 1.

Replace the "3" in that equation with "8- 5": 2(8- 5)- 5= 2(8)- 3(5)= 1.

Multiply both sides by "n": 2n(8)- 3n(5)= n. s= -3n and t= 2n satisfy the equation 5s+ 8t= n.

Answer 2

This is a trivial consequence of Bezout's Theorem wich guarantees that exist $x,y\in \mathbb{Z}$ such that

$$5x+8y=\gcd(5,8)=1\implies 5(nx)+8(ny)=n$$

To find x and y you can proceed by Euclidean Algorithm as in the following example.

Answer 3

First show that there are integers $s_0, t_0$ such that $5s_0+8t_0 = 1$. Now use $s = ns_0, t = nt_0$.