Discrete proofs involving divisibility

[mikky05v]

I'm trying to do some extra course work to prepare for my final next week but I'm having a lot of trouble with the book problems. They talk about a lot of things we weren't taught. Can someone help me out here?

Prove: n$\ni$Z, n= a multiple of gcd(a,b) ⇔ n is a linear combination of a and b

This question makes no sense to me. How do I prove that and where can I start. What does gcd have to do with linear combinations.

 

[gopher_p]

I'm trying to do some extra course work to prepare for my final next week but I'm having a lot of trouble with the book problems. They talk about a lot of things we weren't taught. Can someone help me out here?

Prove: n$\ni$Z, n= a multiple of gcd(a,b) ⇔ n is a linear combination of a and b

This question makes no sense to me. How do I prove that and where can I start. What does gcd have to do with linear combinations.

$n$ is a linear combination of $a$ and $b$ should mean that there exist $s,t\in\mathbb{Z}$ such that $n=sa+tb$.

Write down the precise mathematical meaning of "$n$ is a multiple of $\gcd (a,b)$" and see if that gets you started.

 

[mikky05v]

ok this is what i have
Prove: n∈Z n= a multiple pf gcd(a,b) ⇔ n is a linear combination of a and b
⇒
let gcd(a,b)=d. We are given that n=xd for some x∈Z
Using Bezout’s identity we can expand d, d= sa+tb for some s,t∈Z
Hence, n=xd=x(sa+tb)=xsa+xtb
We recognise this as a linear combination of a and b

now i don't know where to go to do the reverse direction

 

[gopher_p]

ok this is what i have
Prove: n∈Z n= a multiple pf gcd(a,b) ⇔ n is a linear combination of a and b
⇒
let gcd(a,b)=d. We are given that n=xd for some x∈Z
Using Bezout’s identity we can expand d, d= sa+tb for some s,t∈Z
Hence, n=xd=x(sa+tb)=xsa+xtb
We recognise this as a linear combination of a and b

now i don't know where to go to do the reverse direction

Given $n=sa+tb$ and $d=\gcd (a,b)$, what can you say about $n-sa$?

 

[mikky05v]

n-sa=tb where do i go with that?

 

[gopher_p]

Actually, forget that hint ... at least the part about focusing on $n-sa$.

What are you trying to show about $n$ again? What do you know about $a$ and $b$?

 

[mikky05v]

umm I am given n is a linear combination of a,b and I am trying to show that n is a multiple of gcd (a,b)?

 

[gopher_p]

Right. And what do you know about $a$ and $b$ in regards to $\gcd(a,b)$ that might help you establish that $n$ is a multiple of $\gcd(a,b)$? Think about how you might prove that the sum of two even numbers is even.