Well I knew it would come to this......this is going to be a lengthy explanation!

Any number N when expressed in terms of powers of its prime factors takes the form N = a^p * b^q * c^r ........... where a, b, c, ....... are prime numbers and p, q, r, ....... are the the number of powers.
Eg: N = 72 = 2^3 * 3^2
Here a = 2, b = 3 & p = 3, q = 2

There is a formula for finding the sum of all the factors of N. It goes this way: S(Factors of N) =
(a^(p+1) - 1) * (b^(q+1) - 1) * (c^(r+1) - 1) * ........
( a - 1 ) * ( b - 1 ) * ( c - 1 ) * ........

Lets illustrate with the help of an eg why this formula will always yield an odd sum when N is a perfect square.
Say N = 8100 = 2^2 * 3^4 * 5^2

S(Factors of 8100) = { (2^3 - 1) * (3^5 - 1) * (5^3 - 1) } / { (2-1) * (3-1) * (5-1) }

Lets consider the numerator components separately:
(2^3 - 1) = (2-1) * (2^2 + 2 + 1)
(3^5 - 1) = (3-1) * (3^4 + 3^3 + 3^2 + 3 + 1)
(5^3 - 1) = (5-1) * (5^2 + 5 + 1)

(2-1), (3-1) & (5-1) will get canceled from the denominator as well as numerator.

Thus we have,
S(Factors of 8100) = (2^2 + 2 + 1) * (3^4 + 3^3 + 3^2 + 3 + 1) * (5^2 + 5 + 1)
All the 3 expressions above are odd numbers:
(2^2 + 2 + 1) = E + E + O = O ....... Even nos + an odd number = odd
(3^4 + 3^3 + 3^2 + 3 + 1) = O + O + O + O + O = O ....... Sum of an odd no of odd nos is odd
(5^2 + 5 + 1) = O + O + O = O ...... Sum of an odd no of odd nos is odd
where O = Odd & E = Even

Thus we get,
S(Factors of 8100) = O * O * O = O

This will be the case for all perfect squares because perfect square will always have even number of powers of prime factors.
=> Thus S(N) formula will have even + 1 = odd number of powers.
=> For (a^n - b^n) where n is odd there will always be odd no of terms in the expansion as we saw above.
=> The sum of these odd no of odd terms will always be odd. Even in case of (2^odd - 1) there will a string of even nos + one odd no at the end thus making the whole expression odd.
=> Multiplication of these odd nos will always be odd.

Hence proved. Phew!!!!

PS: I wish the old multiple kudos system were still functional !!!!
_________________

KUDOS me if I deserve it !!

My GMAT Debrief - 740 (Q50, V39) | My Test-Taking Strategies for GMAT | Sameer's SC Notes

- 2,3,5 are prime factors but the problem says all distinct factors: 1,2,3,5,6,10,15,18....
- You can see the link in my signature: Comb/Prom - it is a list of links to problems arranged with difficulty level.
_________________

iOS/Android: GMAT ToolKit - The bestselling GMAT prep app | GMAT Club (free) | PrepGame | GRE ToolKit | LSAT ToolKit
PROMO: Are you an exiting GMAT ToolKit (iOS) user? Get GMAT ToolKit 2 (iOS) for free* (read more)
Math: GMAT Math Book ||| General: GMATTimer ||| Chicago Booth: Slide Presentation
The People Who Are Crazy Enough to Think They Can Change the World, Are the Ones Who Do.

How can you demonstrate the the sum of all the factor of a square is odd?

This question is from MGMAT.

Thanks

Hi Walker, could you explain how you concluded that the number of odd factors is odd?
_________________

KUDOS me if I deserve it !!

My GMAT Debrief - 740 (Q50, V39) | My Test-Taking Strategies for GMAT | Sameer's SC Notes

Outstandingly done dude....
Could somebody tell me from where I should study Number Theory and also is there a source of good practice questions for number theory?
Is thr some compilation of number theory questions present on gmatclub....like walker's compilation of probability???

Thanks guys!

Is there any other theory related with squares or powers in general that we should now, apart of this question?

Thanks Guys this is great explanation.

Can some one help, what disintict factors means - would not it be 2,3,5 in case of 8100?

Walker - Can you please guide me how can I get your notes for probability theory.

Thanks guys this awesome forum, handsdown!!

**

n = 2^a*3^b*5^c..... for any positive integer.
N = (1+a)(1+b)(1+c)...gives us the number of distinct factors.
Prime factors: 2,3,5, 7, 11, 13.......
Distinct factors: 1,2,3,5,6,10,15,18....

From Statement 1
Rule: The number of distinct factors of a perfect square is always [highlight]odd[/highlight].
E.g. n=144=(2^4)(3^2) ---> N=(1+4)(1+2)=[highlight]15[/highlight]
Sufficient

From Statement 2
Rule: The sum of all distinct factors of a perfect square is always odd.
Sum(Factors of N) =
(a^(p+1) - 1) * (b^(q+1) - 1) * (c^(r+1) - 1) * ........
( a - 1 ) * ( b - 1 ) * ( c - 1 ) * ........

Sufficient

Answer: D




+1 kudos to walker and samrus98!
_________________

"The best day of your life is the one on which you decide your life is your own. No apologies or excuses. No one to lean on, rely on, or blame. The gift is yours - it is an amazing journey - and you alone are responsible for the quality of it. This is the day your life really begins." - Bob Moawab

Ah, I get it

It might be easier to use smaller numbers:

Factors of 16: 16 8 4 2 1 => number is odd (odd sum of factors)

Factors of 17: 17 1 => even (even sum of factors)

Factors of 4: 4 2 1 => odd (odd sum of factors)

Factors of 6: 6 3 2 1 => even (even sum of factors)
_________________

Staying positive and having fun with the GMAT.

<<====[ If you like my post, press +1 on the left]