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 and $k can not divide $k$.
-
0@DDD, ya, so $k$ can not be . – 2012-10-09