# Discrete proofs involving divisibility

1. Apr 21, 2014

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

2. Apr 21, 2014

### gopher_p

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

3. Apr 21, 2014

### 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

4. Apr 21, 2014

### gopher_p

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

5. Apr 21, 2014

### mikky05v

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

6. Apr 22, 2014

### 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$?

7. Apr 24, 2014

### mikky05v

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

8. Apr 25, 2014

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