6
$\begingroup$

I guess that every prime number occurs as the greatest common divisor of two consecutive square free numbers, which I don't expect a proof of.

But I've done some experiments indicating that:

If $m, n$ are consecutive square free numbers then $\gcd(m, n)$ is not composite.

Is that true and can it be proved?

$\endgroup$
2
  • 1
    $\begingroup$ If $m=p_1p_2k$ and $n=p_1p_2(k+1)$, so that $\gcd(m,n)=p_1p_2$,then you require $p_1p_2-1$ consecutive non-square-free numbers if $m,n$ are to be consecutive square-free positive integers. The smallest that $p_1p_2$ can be is $6$. It is claimed that arbitrarily long sequences of non-square-free numbers occur, but they occur at significantly large magnitudes. See OEIS A045882 $\endgroup$ Commented Jan 13, 2020 at 22:17
  • $\begingroup$ @KeithBackman: It's not just claimed – see the proof in the Wikipedia section I linked to under lulu's answer. $\endgroup$
    – joriki
    Commented Jan 13, 2020 at 22:58

1 Answer 1

16
$\begingroup$

Barring miscalculation we have $$\gcd(28331962460555993122305,28331962460555993122290)=15$$

And these two numbers are consecutive square free integers. Indeed we can obtain the relevant factorings via WA.

This example was constructed out of the Chinese Remainder Theorem, using $$\text {ChineseRemainder}[(0,1,2,3,4,5,6,7,8,10,11,14),$$$$(15,4,7^2,9,11^2,25,13^2,17^2,19^2,23^2,29^2,31^2)]$$ in WA

$\endgroup$
9
  • $\begingroup$ I was just about to start doing the same thing :-) Is there a reason why you used $15$ and not $12=2^2\cdot3$? (I'm aware that $6=2\cdot3$ wouldn't work.) (I mean as the difference of the two numbers, obviously not as their $\gcd$, which would have to be $6$.) $\endgroup$
    – joriki
    Commented Jan 13, 2020 at 22:06
  • $\begingroup$ @joriki Well...when I realized that $6$ failed I gave up on even factors immediately. This might have been too hasty. $\endgroup$
    – lulu
    Commented Jan 13, 2020 at 22:08
  • $\begingroup$ The problem with $6=2\cdot3$ is that it forces one of the numbers to be multiples of $4=2^2$, since there are no other residues of $2$ to move to. But with difference $12=2^2\cdot3$ both numbers can be free of $2^2$. $\endgroup$
    – joriki
    Commented Jan 13, 2020 at 22:09
  • $\begingroup$ Indeed with ChineseRemainder $[(-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11),(5^2,2^2,3^2,7^2,11^2,13^2,17^2,19^2,23^2,29^2,31^2)]$ we get $\gcd(30721170216859104770574,30721170216859104770574+12)=6$. $\endgroup$
    – joriki
    Commented Jan 13, 2020 at 22:13
  • $\begingroup$ @joriki Ah, good. That's better. $\endgroup$
    – lulu
    Commented Jan 13, 2020 at 22:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .