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