2
$\begingroup$

Suppose $b|a$ and $\frac{a}{b} \neq \frac{v}{y}$, $a, b, v, y \in \mathbb{N}$ arbitrary. Is there a nice clean intuitive proof to show that it is never true that $b+yk|a+vk$ for all $k \in \mathbb{N}$? Or is it true sometimes after all (I strongly feel like not)?

$\endgroup$
  • 1
    $\begingroup$ Does $y$ divide $v$ ? For $k=0$, this statement is obviously false .. $\endgroup$ – Astyx Oct 28 '16 at 21:18
  • $\begingroup$ @Astyx It might or it might not. They are arbitrary under the imposed conditions. What do you mean with "for $k=0$ this statement is obviously false"? $k$ is allowed to vary, you just have to find one counter example ,which can be with any $k$, for any $a, b, v, y \in \mathbb{N}$ under the imposed conditions. If I were to allow $\frac{a}{b} = \frac{v}{y}$ then it would be obviously false. $\endgroup$ – Jori Oct 28 '16 at 21:51
  • $\begingroup$ Oh you mean that there always exists k such that $a+vk$ does not divide $b+yk$ ? My bad, I missunderstood your question. $\endgroup$ – Astyx Oct 28 '16 at 21:53
  • $\begingroup$ @Astyx No problem. It seems pretty simple, I wonder what would be a good way to go about proof such statement. Any ideas? My first thought was to say that $a+vk$ will eventually be prime, but that only holds of course if $\gcd(a, v) = 1$ and this we may not assume. $\endgroup$ – Jori Oct 28 '16 at 22:01
2
$\begingroup$

Assume for contradiction that for all $k\in \Bbb N$, $a+vk|b+yk$ and consider the sequence $u_k\in \Bbb Z$ such that $u_k(a+vk) = b+yk$. Then since $u_k = {b+yk\over a+vk} \to {y\over v}$ as $k$ goes to $+\infty$, $u_k$ approaches ${y\over v}$ arbitrary close, which therefore must be an integer, and thus $v|y$. Let $u \in \mathbb{Z}$ be such that $y = vu$. Then for all $k\in \Bbb N$ we have $a+vk |b+vuk$ and therefore also $a+vk |b-au$. However since $a+vk$ is unbounded and $b-au$ does not depend on $k$, what follows is that $b-au = 0$, which rewrites as ${a\over b} = {v \over y}$.

The contrapositive of this is your statement.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you conclude that $y/v$ is an integer?! That directly contradicts the assumption that $y$ and $v$ are chosen arbitrary. $\endgroup$ – Jori Oct 29 '16 at 16:27
  • $\begingroup$ Any sequence of integer that converges converges to an integer $\endgroup$ – Astyx Oct 29 '16 at 16:43
  • $\begingroup$ @Jori I proved the contrapositive of your statement, that is : $(\forall k \in \Bbb N, a+vk|b+yk) \implies {a\over b} = {v \over y}$, leading your statement to be true. $\endgroup$ – Astyx Oct 29 '16 at 16:55
  • $\begingroup$ I read way too fast... my bad. I think that actually works indeed. Nice proof. I found one that depended on Dirichlet theorem on primes in arithmetic progressions, but this is much more elementary. $\endgroup$ – Jori Oct 29 '16 at 17:54
  • $\begingroup$ I do not like my proof because it requires analytic arguments (therefore leaving $\Bbb Z$) to prove such a (seemingly?) simple arithmetic statement, but since it works and I can't think of any other proof ... $\endgroup$ – Astyx Oct 29 '16 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.