Archive for October 19th, 2010

More on unit fractions, greatest common divisors, least common multiples and such

October 19, 2010

Just a quick update, I’ll elaborate later. The technique I used 2 posts ago, in proving that g_n > 1 infinitely often, can be quite easily generalised and yield a lot more that way. And it also gives some insight in why it’s hard to show g_n = 1 infinitely often; maybe it’s not true! The theorem I will prove later (either today or tomorrow) will be:

Let n be a given natural number and p be a given prime. Let a \in \aleph be the unique number smaller than p such that ap^k \le n < (a+1)p^k for some k \in \aleph_0. Then the following two are equivalent:

1) p | X_n
2) p | X_a

Where \dfrac{X_n}{L_n} = \sum_{i=1}^n \dfrac{1}{i}, with L_n the least common multiple of \{1,2,..,n\}

Posted in Problem Solving | Leave a Comment »

Solving a second Erdos-problem (!!)

October 19, 2010

Again: not happy about this post. It seems like I’m terrible at explaining my thoughts on paper. Well, it’s not as if I didn’t know that, but it’s worse than I thought. Anyway, solving two problems of Erdos and Graham in 24 hours is not something I’m not going to blog about;

In their book, Erdös and Graham also ask the following, I think more general, question:

Let \displaystyle \sum_{i=a}^b \dfrac{1}{i} = \dfrac{u_{a,b}}{v_{a,b}}. For fixed a what is the least b = b(a) such that v_{a,b} < v_{a,b-1}? In fact, is there always such a b for every a? Using the result of the previous post, I am able to show that b exists for every a, and, even more, b \le 6a for all a. In a very strict sense this is best possible, as b(1) = 6. I will use the notation from the previous two posts, along with the new definition: X_{a,b} = X_b - X_{a-1}*\dfrac{L_b}{L_{a-1}}. We now have:

\displaystyle \sum_{i = a}^b \dfrac{1}{i}  
= \displaystyle \sum_{i = 1}^b \dfrac{1}{i} - \displaystyle \sum_{i = 1}^{a-1} \dfrac{1}{i}
= \dfrac{X_b}{L_b} - \dfrac{X_{a-1}}{L_{a-1}}
= \dfrac{X_{a,b}}{L_b}

With v_{a,b} = \dfrac{L_b}{(X_{a,b}, L_b)}. Now, let k be such that 3^k \le a < 3^{k+1}. Let b = 2*3^{k+1}. Note that L_b = L_{b-1} in that case. So we’re done if we can show (X_{a,b}, L_b) > (X_{a, b-1}, L_{b-1}). And the proof of this is not very hard using the result of the previous post;

(X_{a, b}, L_b) = (X_b - X_{a-1} \dfrac{L_b}{L_{a-1}}, L_b) = (X_{b-1} + \dfrac{L_b}{b} - X_{a-1} \dfrac{L_b}{L_{a-1}}, L_b)

Now, the only difference with (X_{a, b-1}, L_{b-1}) is the term \dfrac{L_b}{b}. This term doesn’t affect anything, except for possibly factors of 2 and 3 (since b = 2*3^k). But we already know that X_n is odd for all n, which implies X_{a,b} is also odd for all a,b with b \ge 2a. So the only thing that the term \dfrac{L_b}{b} might change, is the divisibility of X_{a,b} by 3. And, indeed, we showed in the previous two posts that (X_{b-1}, 3) = 1 for b = 2*3^k, while (X_b, 3) = 3. So, since 3|\dfrac{L_b}{L_{a-1}} by our choice of b, (X_{a, b-1}, 3) = 1, while (X_{a,b}, 3) = 3. In other words: 3v_{a,b} \le v_{a, b-1}, and this finishes our proof.
To recapture: Let a be fixed. Let k be such that 3^k \le a < 3^{k+1}. Choose b = 2*3^{k+1}. Then: v_{a,b} < v_{a,b-1}

Posted in Problem Solving | Leave a Comment »

Solving an Erdos-problem (!)

October 19, 2010

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.

Posted in Problem Solving | Leave a Comment »