Can anyone help me to solve this problem:

Consider as a natural number greater than . Prove that sum of all numbers of the form with the condition ( and are relatively prime) and and is always equal to

Printable View

- Feb 4th 2010, 12:37 AMhavalizaMath problem
Can anyone help me to solve this problem:

Consider as a natural number greater than . Prove that sum of all numbers of the form with the condition ( and are relatively prime) and and is always equal to - Feb 4th 2010, 08:58 AMqmech
The problem doesn't seem to be right.

Take n=3, p=2, q=3. That's the only combination possible, but 1/pq= 1/6. - Feb 4th 2010, 09:29 AMhavaliza
My bad. I mistyped the problem statement :(

It's instead of

Now it's corrected. - Feb 6th 2010, 03:04 AMhavaliza
Rule #10:

**Do not beg for answers.**If your question is unanswered do not make a post begging for someone to reply back, it is totally useless. Other members can see the question.

But what should i do? I need the answer. I would wonder if anyone help me.

Thnx - Feb 26th 2010, 12:10 PMMedia_ManPrime Induction?
I'll post more later, but fiddling with the problem, I believe it's equivalent to proving the following relation holds for odd prime p and natural k:

= (Wondering)

Prepare for another complicated problem... - Mar 2nd 2010, 06:11 AMMedia_ManSorry for the delay...
Here's where I started. The problem states that for all , , for

Base case : , so

Look at

See if you can notice the pattern. First of all, most pairs stay in the set when moving from to . This is because if they are relatively prime, this has nothing to do with . So, consider the pairs we gain advancing from to , and consider the pairs we lose.

Gain: From to , we gain all pairs

Lose: From to , we lose all pairs

Consider . I observe exactly three cases...

Case 1: , n brings no new factors, so the only pair lost is and the only pairs gained are Example

Case 2: If is prime, . Since n brings exactly one new factor, the pairs gained are and the pairs lost are those of the form for all Example

Case 3: If n is a power of a prime , . So n brings the same gains/losses as case 2, excepting the pairs where the prime (sorry, poor choice of notation). Example

The idea of this approach is that since most of the pairs stay the same, their "part" of the sum remains unchanged. So in jumping from n-1 to n, the part of the sum subtracted from the lost pairs must balance perfectly the part of the sum added by the gained pairs. So for case 1 it is easy to verify the algebraic identity

For case 2, we have the more complicated for n prime

Case 3 is the more complicated formula from my last post. It can easily be seen that case 2 is a special case of 3 for k=1. So if we can prove case 3 the problem is done. However, it may be easier to tackle 2 first to gain enough insight to do 3. - Mar 2nd 2010, 07:36 AMMedia_ManOn second thought...
Actually, turns out is true for all n, not just primes, which makes the remainder of the proof pretty simple. I'll leave you the pleasure of proving the summation.