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 be the least common multiple of and let . Erdos and Graham were interested in ; the greatest common divisor of and , let’s call it . They posed, among many, many more, the following questions (here, page 30 in the pdf-file): Does hold for infinitely many ? Does 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 behaves, by comparing it to and see what can happen for various . I have managed to find the following truths (where always denotes a prime):

1) .

2) (a clear generalization of 1)).

3) if for every prime that divides , holds, then .

4) (implied by 3, but, for me, a lot easier to grasp)

If and can’t be written as with , then .

5) If can’t be written as with , then if, and only if, .

6) is odd

*Proofs.*

In general we have the following:

So . While this may seem messy, it really isn’t; easily simplifies in any case; if is not a prime power, it simplifies to and if , it simplifies to .

*Proof of 2).*

Let . Now:

*Proof of 3).*

Let . Now, since , can’t be a prime power. In particular: . So:

Let be a prime such that . Then, by assumption, . So if is a divisor of , must divide . But ! And since , this is impossible. So .

*Proof of 4).*

If isn’t expressible as with , then, equivalenty, implies . So In particular , which implies . So for every . Furthermore trivially divides and if , as we assumed, must hold. So we may use 3) to show

*Proof of 5).*

Assume can’t be written as with . And since we already covered prime powers, let’s assume isn’t a prime power either. Now: . If , then there is no prime that both divides and . But every prime that divides , also divides . So must equal too. On the other hand, if , then a prime exists that divides both and . And again, every prime that divides , also divides . So now must be at least .

Proof of 6).

Easy exercise 🙂

### Like this:

Like Loading...

*Related*

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.

October 20, 2010 at 20:05 |

[…] 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 […]