Investigating an Erdös-problem

Apologies in advance; I’m not entirely happy about this post. I should have made everything clearer, but somehow that’s hard for me. Anyway, I hope you’re able to understand everything anyway, although it might take you two tries to get what I’m clumsily trying to articulate. As always, if you have any questions, ask me. And if you have any ideas on how to further attack the problem I’m talking about, tell me! Thanks, and enjoy.

Let $L_n$ be the least common multiple of $\{1, 2, .., n\}$ and let $X_n = L_n \sum_{i=1}^n \dfrac{1}{i}$ . Erdos and Graham were interested in $(L_n, X_n)$ ; the greatest common divisor of $L_n$ and $X_n$ , let’s call it $g_n$ . They posed, among many, many more, the following questions (here, page 30 in the pdf-file): Does $g_n = 1$ hold for infinitely many $n$ ? Does $g_n > 1$ hold infinitely often? Clearly, these questions seem too easy to not attack, so I went for it. So far I tried to get a feeling for the way $g_n$ behaves, by comparing it to $g_{n-1}$ and see what can happen for various $n$ . I have managed to find the following truths (where $p$ always denotes a prime):

1) $g_p = g_{p-1}$ .
2) $g_{p^k} = \dfrac{g_{p^k - 1}}{(X_{n-1}, p^{k-1})}$ (a clear generalization of 1)).
3) if for every prime $p$ that divides $n$ , $png_n| L_n$ holds, then $g_n = g_{n-1}$ .
4) (implied by 3, but, for me, a lot easier to grasp)
If $(n, X_n) = 1$ and $n$ can’t be written as $n = ap^k$ with $a \le p - 1$ , then $g_n = g_{n-1}$ .
5) If $n$ can’t be written as $n = ap^k$ with $a \le p - 1$ , then $g_n = 1$ if, and only if, $g_{n-1} = 1$ .
6) $X_n$ is odd

Proofs.
In general we have the following:

$\dfrac{X_{n-1}}{L_{n-1}} + \dfrac{1}{n} = \dfrac{nX_{n-1} + L_{n-1}}{nL_{n-1}} = \dfrac{\dfrac{n}{(n, L_{n-1})}X_{n-1} + \dfrac{L_{n-1}}{(n, L_{n-1})}}{L_n}$
So $X_n = \dfrac{nX_{n-1}+ L_{n-1}}{(n, L_{n-1})}$ . While this may seem messy, it really isn’t; $(n, L_{n-1})$ easily simplifies in any case; if $n$ is not a prime power, it simplifies to $n$ and if $n = p^k$ , it simplifies to $p^{k-1}$ .

Proof of 2).
Let $n = p^k$ . Now: $g_n = (X_n, L_n) = (pX_{n-1} + \dfrac{L_{n-1}}{p^{k-1}}, pL_{n-1})$
$= (pX_{n-1} + \dfrac{L_{n-1}}{p^{k-1}}, p^{k+1}X_{n-1}) = (pX_{n-1} + \dfrac{L_{n-1}}{p^{k-1}}, X_{n-1})$
$= (\dfrac{L_{n-1}}{p^{k-1}}, X_{n-1}) = \dfrac{g_{n-1}}{(X_{n-1}, p^{k-1})}$

Proof of 3).
Let $X_n' = \dfrac{X_n}{g_n}, L_n' = \dfrac{L_n}{g_n}$ . Now, since $pn | L_n$ , $n$ can’t be a prime power. In particular: $L_n = L_{n-1}$ . So:

$g_n = (X_n, L_n) = (X_{n-1} + \dfrac{L_{n-1}}{n}, L_{n-1}) =(X_{n-1} + \dfrac{L_{n-1}}{n}, nX_{n-1})$
$=g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, nX_{n-1}') = g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, n).$

Let $p$ be a prime such that $p | n$ . Then, by assumption, $p| \dfrac{L_{n-1}'}{n}$ . So if $p$ is a divisor of $g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, n)$ , $p$ must divide $X_{n-1}'$ . But $(X_{n-1}', L_{n-1}) = 1$ ! And since $p | L_{n-1}$ , this is impossible. So $g_n = g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, n) = g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, 1) = g_{n-1}$ .

Proof of 4).
If $n$ isn’t expressible as $ap^k$ with $a \le p-1$ , then, equivalenty, $n = ap^k$ implies $a > p$ . So In particular $p^{k+1} < n$ , which implies $p^{k+1} | L_n$ . So $pn | L_n$ for every $p | n$ . Furthermore $g_n$ trivially divides $L_n$ and if $(n, g_n) = 1$ , as we assumed, $png_n | L_n$ must hold. So we may use 3) to show $g_n = g_{n-1}$

Proof of 5).
Assume $n$ can’t be written as $n = ap^k$ with $a \le p-1$ . And since we already covered prime powers, let’s assume $n$ isn’t a prime power either. Now: $g_n = (X_n, L_n) = (X_{n-1} + \dfrac{L_{n-1}}{n}, L_{n-1})$ . If $g_{n-1} = 1$ , then there is no prime that both divides $X_{n-1}$ and $L_{n-1}$ . But every prime that divides $L_{n-1}$ , also divides $\dfrac{L_{n-1}}{n}$ . So $g_n$ must equal $1$ too. On the other hand, if $g_{n-1} > 1$ , then a prime $p_1$ exists that divides both $X_{n-1}$ and $L_{n-1}$ . And again, every prime that divides $L_{n-1}$ , also divides $\dfrac{L_{n-1}}{n}$ . So now $g_n$ must be at least $p_1 > 1$ .

Proof of 6).
Easy exercise 🙂

This entry was posted on October 17, 2010 at 18:30 and is filed under Problem Solving. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Investigating an Erdös-problem”

More sensible heuristics « Woett's Blog Says:
October 20, 2010 at 20:05 | Reply
[…] not familiar with the problem I’m semipublicly trying to solve, please start reading here. Coming to think about it, this is basically just another polymath-project. With the only […]

Woett's Blog

Investigating an Erdös-problem

Share this:

Like this:

Related

One Response to “Investigating an Erdös-problem”

Leave a Reply Cancel reply