Alright, I answered one of the questions asked in the previous post in the affirmative; Let be the least common multiple of . Let . Let be the greatest common divisor of and .

Question: Does happen infinitely often?

Answer: Yes!

*Proof.*

First of all, if is not a prime power, there are possibilities: Either , or , with ; We have and is always divisible by , unless , with . Furthermore, since statement 2) in the previous post implies that for a power of we have , we actually have for every with . We shall show that for , which implies that for every with . And, clearly, there are infinitely many of them.

Let everything be defined as above, let and let be the greatest common divisor of and . Since , we have that . Since by the definition of and , we have that and must be equal modulo (because if they’re different, then their sum, which equals , must be divisible by , in which case we’re done). So we have:

But every term except in the last sum vanishes modulo ;

Multiplying by 2 gives the impossible conclusion:

So we must have that and are different (while both non-zero) modulo . So their sum, better known as , is divisible by . Q.E.D.

### Like this:

Like Loading...

*Related*

This entry was posted on October 19, 2010 at 00:27 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.

## Leave a Reply