1

For $a<b$, prove that every block of $b$ consecutive naturals, there are two distinct naturals whose product is divisible by $ab$. [I believe I can do this: see below]

Now, for $a<b<c$, is it true that in every block of $c$ consecutive naturals there are three distinct naturals whose product is divisible by $abc$?

Informal attempt for part 1: In $b$ consecutive integers there must be a multiple of $a$ and a multiple of $b$, since $a<b$. If they are the same, I've shown that you can select the next multiple of $a$ in the block and thus we have a product divisible by $ab$. EDIT: there isn't necessarily another multiple of $a$ but I can now show a multiple of $gcd(a,b)$.

Please answer both parts of the question, if you would like to, and certainly criticise my informal attempt where necessary. I am more interested in the second part however: my friend who gave this to me was ambiguous about whether it's actually true, so possibly I actually need to prove it's false.

I have noticed this question has been asked before, but one of the questions was abandoned because the questioner was rude, and for the other, no answer was actually reached, so I was hoping another attempt might be made.

Thank you very much for your consideration.

John Smith
  • 628
  • Let $a = 2$ and $b = 4$. Take the block of length four $3,4,5,6$ and be so kind to point me towards the number in there divisible by $2\cdot 4 = 8$... – Dirk Aug 25 '17 at 10:28
  • @DirkLiebhold The OP only requires that the block contain two numbers whose product is divisible by $ab$. In your block, $4\times 6$ fits the bill. – lulu Aug 25 '17 at 10:49
  • 1
    I think your proof of the first question is not valid. The "next multiple of $a$" may not exist in the block, unless $b\geq 2a$. However, it is sufficient to show that there exists another number in the block divisible by $\gcd(a,b)$. – Batominovski Aug 25 '17 at 11:32
  • Thank you @Batoninovski, my mistake. I realised a few hours ago but I haven't been able to update it until now. – John Smith Aug 25 '17 at 14:41
  • trivially true if you let $a=1$ – MaximusFastidiousIrreverence Aug 26 '17 at 16:13

1 Answers1

1

In any set $S$ of $b$ consecutive naturals, there is exactly one element that is a multiple of $b$ - call it $x$, say.

There are three cases:

  • $x$ is not a multiple of $a$. In this case there exists at least one element of $S$ that is divisible by $a$ and is not $x$.
  • $x$ is a multiple of $a$, and $a$ and $b$ are coprime. In this case, as $a$ and $b$ are coprime, $x$ must be a multiple of $ab$, so you can pick any other element of $S$.
  • $x$ is a multiple of $a$, and $a$ and $b$ are not coprime, having a $\gcd$ of $g$. In this case, $x$ must be divisible by $ab/g$, since $a/g$ and $b/g$ are coprime. So we simply have to find another multiple of $g$ within our set, which is always possible since there must be at least $\lfloor b/g\rfloor$ multiples of $g$ in any set of $b$ consecutive naturals, and $b/g \ge 2$ so there is always at least $1$ other multiple of $g$.
Tez LaCoyle
  • 1,476
  • 7
  • 7
  • Thank you very much for this answer. It is clear and concise. – John Smith Aug 25 '17 at 14:46
  • Before I accept it however, if possible I would like to see if someone will attempt the second part of my question. @T.Linnell, would you attempt it please? – John Smith Aug 25 '17 at 14:47