Find all School-related info fast with the new School-Specific MBA Forum

It is currently 26 Jul 2014, 11:49

Close

GMAT Club Daily Prep

Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.

Events & Promotions

Events & Promotions in June
Open Detailed Calendar

Is the positive integer N a perfect square?

  Question banks Downloads My Bookmarks Reviews Important topics  
Author Message
TAGS:
2 KUDOS received
Senior Manager
Senior Manager
avatar
Joined: 22 Sep 2005
Posts: 280
Followers: 1

Kudos [?]: 37 [2] , given: 1

GMAT Tests User
Is the positive integer N a perfect square? [#permalink] New post 13 Aug 2009, 05:49
2
This post received
KUDOS
00:00
A
B
C
D
E

Difficulty:

  25% (medium)

Question Stats:

63% (01:30) correct 38% (00:42) wrong based on 64 sessions
Is the positive integer N a perfect square?

(1) The number of distinct factors of N is even.
(2) The sum of all distinct factors of N is even.

OPEN DISCUSSION OF THIS QUESTION IS HERE: is-the-positive-integer-n-a-perfect-square-1-the-number-79108.html
[Reveal] Spoiler: OA

Last edited by Bunuel on 30 Jul 2012, 03:36, edited 1 time in total.
OA added.
Kaplan Promo CodeKnewton GMAT Discount CodesManhattan GMAT Discount Codes
3 KUDOS received
Manager
Manager
avatar
Joined: 25 Jul 2009
Posts: 117
Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN
Followers: 4

Kudos [?]: 138 [3] , given: 17

GMAT Tests User
Re: Factors [#permalink] New post 13 Aug 2009, 06:56
3
This post received
KUDOS
Is the positive integer N a perfect square?

(1) The number of distinct factors of N is even.
(2) The sum of all distinct factors of N is even.



SOL:

St1:
Tip: If the number of distinct factors is even, then N cannot be a perfect square. The number of distinct factors of a perfect square is always odd. Remember this!!
=> SUFFICIENT

St2:
Tip: If the sum of all distinct factors of N is even, then N cannot be a perfect square. The sum of all distinct factors of a perfect square is always odd. Remember this too!!
=> SUFFICIENT

ANS: D
_________________

KUDOS me if I deserve it !! :)

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

Manager
Manager
avatar
Joined: 25 Jul 2009
Posts: 117
Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN
Followers: 4

Kudos [?]: 138 [0], given: 17

GMAT Tests User
Re: Factors [#permalink] New post 13 Aug 2009, 07:00
Btw where did you find this question? I am intrigued!
_________________

KUDOS me if I deserve it !! :)

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

Senior Manager
Senior Manager
avatar
Joined: 22 Sep 2005
Posts: 280
Followers: 1

Kudos [?]: 37 [0], given: 1

GMAT Tests User
Re: Factors [#permalink] New post 13 Aug 2009, 09:44
How can you demonstrate the the sum of all the factor of a square is odd?

This question is from MGMAT.

Thanks
5 KUDOS received
Manager
Manager
avatar
Joined: 25 Jul 2009
Posts: 117
Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN
Followers: 4

Kudos [?]: 138 [5] , given: 17

GMAT Tests User
Re: Factors [#permalink] New post 13 Aug 2009, 10:59
5
This post received
KUDOS
netcaesar wrote:
How can you demonstrate the the sum of all the factor of a square is odd?

This question is from MGMAT.

Thanks



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 :P !!!!
_________________

KUDOS me if I deserve it !! :)

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

Expert Post
CEO
CEO
User avatar
Joined: 17 Nov 2007
Posts: 3604
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth) - Class of 2011
GMAT 1: 750 Q50 V40
Followers: 351

Kudos [?]: 1690 [0], given: 354

GMAT ToolKit User GMAT Tests User Premium Member
Re: Factors [#permalink] New post 13 Aug 2009, 12:55
Expert's post
Kudos, guys, for the good question and explanation.
My approach:

n = 2^a*3^b*5^c..... - any positive integer.
N = (1+a)(1+b)(1+c) - number of distinct factors.
to be perfect square, all a, b, c ... for N must be even.

1) The number of distinct factors of N is even.
N = (1+even)(1+even)... - always odd.

(2) The sum of all distinct factors of N is even.
the sum of even factors will be always even but if the number of odd factors is odd, the sum will be odd. Let's see what we have for perfect square:
exclude any power of 2: The number of odd factors of N --> (1)(odd)(odd)... = odd
So, we always have odd number of odd factors for a perfect square. Therefore, the sum of all factors will be also odd.
_________________

HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android) - The OFFICIAL GMAT CLUB PREP APP, a must-have app especially if you aim at 700+ | PrepGame

Manager
Manager
avatar
Joined: 25 Jul 2009
Posts: 117
Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN
Followers: 4

Kudos [?]: 138 [0], given: 17

GMAT Tests User
Re: Factors [#permalink] New post 13 Aug 2009, 13:34
walker wrote:
Kudos, guys, for the good question and explanation.
My approach:

n = 2^a*3^b*5^c..... - any positive integer.
N = (1+a)(1+b)(1+c) - number of distinct factors.
to be perfect square, all a, b, c ... for N must be even.

1) The number of distinct factors of N is even.
N = (1+even)(1+even)... - always odd.

(2) The sum of all distinct factors of N is even.
the sum of even factors will be always even but if the number of odd factors is odd, the sum will be odd. Let's see what we have for perfect square:
exclude any power of 2: The number of odd factors of N --> (1)(odd)(odd)... = odd
So, we always have odd number of odd factors for a perfect square. Therefore, the sum of all factors will be also odd.


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

Expert Post
CEO
CEO
User avatar
Joined: 17 Nov 2007
Posts: 3604
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth) - Class of 2011
GMAT 1: 750 Q50 V40
Followers: 351

Kudos [?]: 1690 [0], given: 354

GMAT ToolKit User GMAT Tests User Premium Member
Re: Factors [#permalink] New post 13 Aug 2009, 14:17
Expert's post
samrus98 wrote:
Hi Walker, could you explain how you concluded that the number of odd factors is odd?


Maybe I don't clearly understand what you are asking... 1*odd*odd... is always odd as all numbers in the product are odd numbers.
_________________

HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android) - The OFFICIAL GMAT CLUB PREP APP, a must-have app especially if you aim at 700+ | PrepGame

Intern
Intern
avatar
Joined: 11 Aug 2009
Posts: 4
Followers: 0

Kudos [?]: 0 [0], given: 6

Re: Factors [#permalink] New post 14 Aug 2009, 10:39
samrus98 wrote:
netcaesar wrote:
How can you demonstrate the the sum of all the factor of a square is odd?

This question is from MGMAT.

Thanks



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
..............
=> Multiplication of these odd nos will always be odd.

Hence proved. Phew!!!!

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



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???
Manager
Manager
avatar
Joined: 25 Jul 2009
Posts: 117
Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN
Followers: 4

Kudos [?]: 138 [0], given: 17

GMAT Tests User
Re: Factors [#permalink] New post 14 Aug 2009, 10:44
gauravc wrote:
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???


You could start with Manhattan Strategy guide on Numbers for theory.
_________________

KUDOS me if I deserve it !! :)

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

Senior Manager
Senior Manager
avatar
Joined: 22 Sep 2005
Posts: 280
Followers: 1

Kudos [?]: 37 [0], given: 1

GMAT Tests User
Re: Factors [#permalink] New post 14 Aug 2009, 11:44
Thanks guys!

Is there any other theory related with squares or powers in general that we should now, apart of this question?
Manager
Manager
avatar
Joined: 25 Jul 2009
Posts: 117
Schools: NYU, NUS, ISB, DUKE, ROSS, DARDEN
Followers: 4

Kudos [?]: 138 [0], given: 17

GMAT Tests User
Re: Factors [#permalink] New post 14 Aug 2009, 12:03
netcaesar wrote:
Thanks guys!

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



There could be things derived from the basic formulae and theory.....but I guess this covers more than decent part of it....
_________________

KUDOS me if I deserve it !! :)

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

Manager
Manager
avatar
Joined: 12 Aug 2009
Posts: 107
Followers: 3

Kudos [?]: 12 [0], given: 2

Reviews Badge
Re: Factors [#permalink] New post 14 Aug 2009, 18:56
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!!
Expert Post
1 KUDOS received
CEO
CEO
User avatar
Joined: 17 Nov 2007
Posts: 3604
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth) - Class of 2011
GMAT 1: 750 Q50 V40
Followers: 351

Kudos [?]: 1690 [1] , given: 354

GMAT ToolKit User GMAT Tests User Premium Member
Re: Factors [#permalink] New post 14 Aug 2009, 20:30
1
This post received
KUDOS
Expert's post
dolly12 wrote:
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!!


- 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.
_________________

HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android) - The OFFICIAL GMAT CLUB PREP APP, a must-have app especially if you aim at 700+ | PrepGame

Manager
Manager
avatar
Status: GMAT in 4 weeks
Joined: 28 Mar 2010
Posts: 186
GPA: 3.89
Followers: 1

Kudos [?]: 35 [0], given: 25

GMAT Tests User
Re: Factors [#permalink] New post 18 May 2011, 10:52
very very good question ..
Thanks for posting
_________________

If you liked my post, please consider a Kudos for me. Thanks!

Manager
Manager
User avatar
Joined: 20 Jul 2011
Posts: 152
GMAT Date: 10-21-2011
Followers: 0

Kudos [?]: 31 [0], given: 15

GMAT Tests User
Re: Factors [#permalink] New post 05 Sep 2011, 12:06
**
Quote:
Is the positive integer N a perfect square?

(1) The number of distinct factors of N is even.
(2) The sum of all distinct factors of N is even.


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


Quote:
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.


+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

Manager
Manager
User avatar
Joined: 13 Apr 2010
Posts: 173
Location: singapore
Schools: Wharton,NY Stern,INSEAD,Stanford
Followers: 2

Kudos [?]: 28 [0], given: 25

GMAT ToolKit User GMAT Tests User
Re: Factors [#permalink] New post 05 Sep 2011, 22:14
Very good question.
Thanks for posting
_________________

Regards,
Nagesh
My GMAT Study Plan: my-gmat-study-plan-112833.html
Idioms List : gmat-idioms-104283.html?hilit=idioms#p813231
--------------------------------------
Consider Kudos if you like my posts

Manager
Manager
avatar
Joined: 22 Jan 2011
Posts: 59
Location: London, UK
Followers: 1

Kudos [?]: 6 [0], given: 17

GMAT ToolKit User GMAT Tests User
Re: Factors [#permalink] New post 06 Sep 2011, 06:12
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]

Re: Factors   [#permalink] 06 Sep 2011, 06:12
    Similar topics Author Replies Last post
Similar
Topics:
Experts publish their posts in the topic Is the positive integer N a perfect square? (1) The number mojorising800 2 10 Jul 2011, 23:26
4 Experts publish their posts in the topic If the positive integer N is a perfect square, which of the Orange08 17 25 Sep 2010, 10:37
9 Experts publish their posts in the topic Is the positive integer N a perfect square? PTK 13 23 May 2010, 11:02
1 Is the positive integer N a perfect square? (1) The number noboru 2 27 Jul 2009, 14:27
25 Experts publish their posts in the topic Is the positive integer N a perfect square? (1) The number mbaMission 23 02 Jun 2009, 04:18
Display posts from previous: Sort by

Is the positive integer N a perfect square?

  Question banks Downloads My Bookmarks Reviews Important topics  


GMAT Club MBA Forum Home| About| Privacy Policy| Terms and Conditions| GMAT Club Rules| Contact| Sitemap

Powered by phpBB © phpBB Group and phpBB SEO

Kindly note that the GMAT® test is a registered trademark of the Graduate Management Admission Council®, and this site has neither been reviewed nor endorsed by GMAC®.