Coprimality via converse of Euclid's Lemma 
Let $x,y \in \mathbb Z$ be fixed with $x\neq 0$. Suppose we have the following: For all $k\in \mathbb Z$, if $x\mid ky$, then $x\mid k$. Prove that $x$ and $y$ are relatively prime.

This reminds me of the Fundamental Theorem of Arithmetic - but its inverse.
I want to use proof by contradiction.
Suppose that $\gcd (x,y)\neq 1$, then $\frac {x}{\gcd(x,y)}$ and $\frac {y}{\gcd(x,y)}$ are relatively prime. 
So there are integers $a$ and $b$ such that $$\frac {ax}{\gcd(x,y)}+\frac {by}{\gcd(x,y)} = 1.$$
How do I continue?
Thank you!
 A: Let us prove the contrapositive.  Suppose $\gcd(x,y)=d>1$.  Then we will construct an integer $k$ such that $x\,|\,ky$ but $x\nmid k$.
Indeed, write $x=dX, y=dY$.  Then $x\,|\,Xy$ since $Xy=(Xd)\times Y=xY$ but $x\nmid X$.
And we are done.
A: We give proofs that highlight the relationship with gcd & lcm, then show how they generalize.
Our hypothesis is $\, x\mid ky\ \Longrightarrow\  x\mid k,\ $ for all $\,k\in\Bbb Z$
thus $\,\ \color{#c00}{d\mid x,y}\,\Rightarrow\, x^{\phantom{|^{|^|}}}\!\!\!\mid  \smash{(\overbrace{x/d}^{\large k})}y\,\Rightarrow\, x\mid x/d\,\Rightarrow\, \color{#c00}{d\mid 1}\ \ $  [or use the dual proof below]

Or: $\,\ \color{#0a0}{x,y\mid n}\,\Rightarrow\, x\mid(\underbrace{n/y}_{\large k})y\,\Rightarrow\, x\mid n/y\,\Rightarrow\, \color{#0a0}{xy\mid n},\ $ so $\ {\rm lcm}(x,y)=\color{#0a0}{xy}\,\Rightarrow\,\gcd(x,y)=1$

As suggested above this property is closely related to various notions of "$x,y$ are coprime". In fact it is equivalent to scaled versions of the above, as we show below.
Theorem $ $ TFAE notions of "$x,y\,$ are coprime" for $\,x,y \in Z^*,\,$ in any domain $Z,\,$ e.g. $\,\Bbb Z$.
$(1) \ \ \ \forall\, k\in Z^*\!:\,\ \ \ \ \ \ \ \ \ \ \ \ \ \ x\mid ky\,\Rightarrow\, x\mid k\ \ \ \ \ \ \ \ \ \ [\![\rm Euclid\ Lemma\ form]\!]$
$(2) \ \ \ \forall\, k,n\in Z^*\!:\,\ \ \  kx,ky\mid n\,\Rightarrow\, kxy\mid n\ \ \ \ \ \ [\![\rm LCM\ form]\!]$
$(3) \ \ \ \forall\, k,n\in Z^*\!:\ \ \ \ n\mid kx,ky\,\Rightarrow\, n\mid k \ \ \ \ \ \ \ \ \ \ [\![\rm GCD\ form]\!].\quad {\bf Proof}\!:$

$(1\Rightarrow 2)\ \ \ kx,ky\mid n\: \Rightarrow\: x\mid n/(ky)\,y\, \ \smash{\overset{(1)}\Rightarrow}\,\ x\mid n/(ky)\Rightarrow\, kxy\mid n$
$(2\Rightarrow 3)\ \ \ n\mid kx,ky\,\Rightarrow\,nx,ny\mid kxy\,\ \smash{\overset{(2)}\Rightarrow}\ \, nxy\mid kxy\,\Rightarrow\,n\mid k\ \ \ $
$(3\Rightarrow 1)\ \ \ x\mid ky\,\Rightarrow\,x\mid kx, ky\,\ \smash{\overset{(3)}\Rightarrow}\ \,x\mid k$

Note that $(2)$ and $(3)$ apply in any domain (where lcms and gcds need not  generally exist), but they may be expressed as the existence of the following lcm and gcd (hence the names).
$(2) \ \ \ \forall\, k,n\in Z^*\!:\,\ \ \  kx,ky\mid n\,\Rightarrow\, kxy\mid n\ \  \iff \ \ {\rm lcm}(kx,ky) = kxy$
$(3) \ \ \ \forall\, k,n\in Z^*\!:\ \ \ \ n\mid kx,ky\,\Rightarrow\, n\mid k  \ \ \ \ \ \ \iff\  \gcd(kx,ky) = k$
A: Let $d=\gcd(x,y)$. Then, $$x\mid yk\Leftrightarrow$$ $$\frac xd\bigm\vert\frac yd k\Leftrightarrow$$ $$\frac xd\bigm\vert k.$$ So, if $d\neq1$, any multiple of $\frac xd$ not also a multiple of $x$ provides a counterexample.
