# If $a, b \in \mathbb{N}$ are relatively prime and $a < b$, then $ka$ can't be a multiple of $b$ for $k < a$.

The statement in the title seems obviously true to me, but I can't quite prove it. Any suggestions would be appreciated.

-

Hint $\$ By Euclid's Lemma $\rm\ (b,a)=1,\,\ b\:|\:ak\:\Rightarrow\:b\:|\:k\:\Rightarrow\: b \le k < a$

-

If $ka$ is a multiple of $b, ka=bc$ for some integer $c$.

$\implies c=\frac{ka}{b} \implies b\mid k$ as $(a,b)=1$

But as $a<b$ and $k<a\implies k<b, b$ can not divide $k$.

-
I also just realized that my statement follows from the fact lcm(a, b) = ab. –  DDD Oct 9 '12 at 6:02
@DDD, ya, so $k$ can not be $<b$. –  lab bhattacharjee Oct 9 '12 at 6:36