Prove that ∀d ∈ N − {0, 1} ∃a, b, u, v ∈ Z − {0} (ua + vb = d ∧ gcd(a, b) ≠ d)

I have to prove this particular statement:

$\forall d \in \mathbb{N}-\{0,1\}\hspace{1em}\exists a,b,u,v \in \mathbb{Z}-\{0\}\hspace{1em}(ua+vb=d~\wedge~gcd(a,b)≠d)$

What's the best way to start off?
I always have that problem with proofs, I never know which facts can be assumed true and which require further proving.

• think about choosing some particular values for $a,b,v,u$ e.g. a=1,b=1,v=1, u=d-1. – Anurag A Nov 8 '15 at 9:21