Solving an Erdos-problem (!)

Alright, I answered one of the questions asked in the previous post in the affirmative; Let L_n be the least common multiple of \{1, 2, .., n\}. Let X_n = L_n \sum_{i=1}^n \dfrac{1}{i}. Let g_n be the greatest common divisor of L_n and X_n

Question: Does g_n > 1 happen infinitely often?

Answer: Yes!

Proof.
First of all, if n is not a prime power, there are 2 possibilities: Either X_n \equiv X_{n-1} \pmod{p}, or n = ap^k, with 2 \le a \le p - 1; We have X_n = X_{n-1} + \dfrac{L_{n-1}}{n} and \dfrac{L_{n-1}}{n} is always divisible by p, unless n = ap^k, with a \le p-1. Furthermore, since statement 2) in the previous post implies that for n a power of 3 we have (g_n, 3) = 1, we actually have (g_n, 3) = 1 for every n with 3^k \le n \le 2*3^k - 1. We shall show that (g_n, 3) = 3 for n = 2*3^k, which implies that for every n with 2*3^k \le n \le 2*3^{k+1} - 1. And, clearly, there are infinitely many of them.

Let everything be defined as above, let n = 2*3^k and let (y, z) be the greatest common divisor of y and z. Since L_{n-1} = L_n, we have that X_n = X_{n-1} + \dfrac{L_n}{n}. Since (\dfrac{L_n}{n}, 3) = 1 by the definition of n and (X_{n-1}, 3) = 1, we have that \dfrac{L_n}{n} and X_{n-1} must be equal modulo 3 (because if they’re different, then their sum, which equals X_n, must be divisible by 3, in which case we’re done). So we have:

\dfrac{L_n}{n} \equiv X_{n-1} \equiv L_{n-1} \sum_{i=1}^{n-1} \dfrac{1}{i} \equiv L_n \sum_{i=1}^{n-1} \dfrac{1}{i} \pmod{3}

But every term except \dfrac{1}{3^k} in the last sum vanishes modulo 3;

\dfrac{L_n}{2*3^k} = \dfrac{L_n}{n} \equiv L_n \sum_{i=1}^{n-1} \dfrac{1}{i} \equiv \dfrac{L_n}{3^k} \pmod{3}

Multiplying by 2 gives the impossible conclusion:

\dfrac{L_n}{3^k} \equiv 2 * \dfrac{L_n}{3^k} \pmod{3}

So we must have that \dfrac{L_{n-1}}{n} and X_{n-1} are different (while both non-zero) modulo 3. So their sum, better known as X_n, is divisible by 3. Q.E.D.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: