1
$\begingroup$

I am trying to prove that for all $N>1$, the number of divisors of the lowest common multiple of the first $N$ natural numbers is divisible by twice the number of distinct prime factors of $N$.

$$2\,\omega(N)\, | \,\tau(\operatorname{lcm}(1,2,3,...,N))\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(0)$$

For the greater proportion of naturals, this can be seen as a consequence of the number of divisors of $N$ being divisible by the number of it's unique prime factors, the density of these values when compared to it's complement (the number of divisors of $N$ being not being divisible by the number of it's unique prime factors) being relatively high. OEIS entry relevant

Then the factor of 2 can be seen as evident in observing that all values of $\tau(\operatorname{lcm}(1,2,3,...,N))$ appear to be even, so a preliminary lemma requiring proof is to show that $\operatorname{lcm}(1,2,3,...,N)$ must always have an even number of divisors, therefore also an even number of proper divisors greater than $1$ as well.

Any natural number $N$ has a unique prime factorization product: $$N=p_{1,N}^{v_{1,N}}p_{2,N}^{v_{2,N}}p_{3,N}^{v_{3,N}}\cdot\cdot\cdot p_{\omega(N),N}^{v_{\omega(N),N}}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(1)$$

$$\mathfrak L=\operatorname{lcm}(1,2,3,...,N)=p_{1,\mathfrak L}^{v_{1,\mathfrak L}}p_{2,\mathfrak L}^{v_{2,\mathfrak L}}p_{3,\mathfrak L}^{v_{3,\mathfrak L}}\cdot\cdot\cdot p_{\omega(\mathfrak L),\mathfrak L}^{v_{\omega(\mathfrak L),\mathfrak L}}$$ So in light of the number of divisors given by: $$\tau(\mathfrak L)=\prod_{j=1}^{\omega(\mathfrak L)}(v_{j,\mathfrak L}+1)$$

We know that the lowest common multiple of the first $N$ natural numbers must have at least one prime factor with an odd multiplicity in order for it's number of divisors to be even.

So that is as far as ive got as well as starting to making considerations of previous study on this topic which I will link here

I'm really just looking for a hint please.

$\endgroup$
  • $\begingroup$ This seems obvious but hard to prove. $\omega(N)$ is tiny, so it divides a lot of things that are made my multiplying factors. If we take $N=30$ to get three prime factors we need $6$ to divide the right side, which means we need one prime factor of the LCM to be to the first power and one to the second power. This will be true if there is a prime between $\sqrt N$ and $N$ and another between $\sqrt[3]N$ and $\sqrt N$. In the case of $30$ we have lots of choices for the first and $5$ satisfies the second. Once $N\gt 64$ we know there is a prime in the range by Bertrand. $\endgroup$ – Ross Millikan Aug 15 '18 at 18:04
  • $\begingroup$ Sure I agree that $\omega(N)$ dividing something would not usually mean much, I suppose the reason this captured my interest was that $\frac{\tau(N)}{\omega(N)}$ has non integer values where as $\frac{\tau(\operatorname{lcm}(1,2,3...,N))}{\omega(N)}$ doesn't. $\endgroup$ – Adam Aug 15 '18 at 18:10
  • 1
    $\begingroup$ I think you can use the formula for the minimum value of $N$ with $k$ prime factors. The factor $2$ on the left comes for free. The factor $k$ demands there be a prime between $\sqrt[k] N$ and $\sqrt[k-1] N$ Because $N$ is so large I think you can guarantee one by Bertrand's postulate. For $k=5$ the smallest $N$ is $2310$ and again $5$ works but the range of the roots is too small for Bertrand. $\endgroup$ – Ross Millikan Aug 15 '18 at 18:10
4
$\begingroup$

$2\cdot 3\cdot 5\cdot 7\cdot 13\cdot 17\cdot 19 = 881790$ doesn't appear to qualify - there are no $6$th, $13$th or $20$th powers in the LCM.

$\endgroup$
  • $\begingroup$ ok so can you please show me the working for how you determined that those powers are not in the LCM $\endgroup$ – Adam Aug 15 '18 at 18:38
  • 1
    $\begingroup$ @Adam LCM will consist of the highest prime powers for each prime present in the numbers up to $N$. So $\left\lfloor\log_p N\right\rfloor$ will give this for each prime. $\endgroup$ – Joffan Aug 15 '18 at 18:42
  • $\begingroup$ oh I ok yes of course I see what you mean now thanks $\endgroup$ – Adam Aug 15 '18 at 18:45
  • $\begingroup$ I'm just glad I posted this question instead of wasting the rest of my morning trying to prove a false statement $\endgroup$ – Adam Aug 15 '18 at 18:50
  • $\begingroup$ Sorry I would also greatly appreaciate your opinion here if you have time please @Joffan math.stackexchange.com/questions/2814343/… I have been trying to understand these approximations in the context of the first Chebyshev function asymptotically also approach the same value $\endgroup$ – Adam Aug 15 '18 at 18:59

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.