The statement in the title seems obviously true to me, but I can't quite prove it. Any suggestions would be appreciated.
If $a, b \in \mathbb{N}$ are relatively prime and $a < b$, then $ka$ can't be a multiple of $b$ for $k < a$.
1
$\begingroup$
elementary-number-theory
2 Answers
2
Hint $\ $ By Euclid's Lemma $\rm\ (b,a)=1,\,\ b\:|\:ak\:\Rightarrow\:b\:|\:k\:\Rightarrow\: b \le k < a$
1
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
-
1I also just realized that my statement follows from the fact lcm(a, b) = ab. – 2012-10-09
-
0@DDD, ya, so $k$ can not be $ – 2012-10-09