# divisibility

• Apr 2nd 2010, 02:44 PM
ihavvaquestion
divisibility
I have attached a problem that deals with divisibility. How do i figure this out without going through all 36 steps of brute force?
• Apr 2nd 2010, 04:49 PM
tonio
Quote:

Originally Posted by ihavvaquestion
I have attached a problem that deals with divisibility. How do i figure this out without going through all 36 steps of brute force?

Hint: what natural numbers have an odd number of positive divisors? (Yes, do some examples and then try to deduce a general rule...and prove it! At least for naturals up to 36)

Tonio
• Apr 2nd 2010, 05:22 PM
ihavvaquestion
hey tonio...thanks

so it looks like 1,4,9,16,25,and 36 all have an odd number of divisors.

so the students who properly followed the teachers instructions, that were still standing, all must have picked a whole numbers' square...is that correct?
• Apr 2nd 2010, 07:15 PM
tonio
Quote:

Originally Posted by ihavvaquestion
hey tonio...thanks

so it looks like 1,4,9,16,25,and 36 all have an odd number of divisors.

so the students who properly followed the teachers instructions, that were still standing, all must have picked a whole numbers' square...is that correct?

Yep. Now try to do a little research in google about divisors of natural numbers and you'll find there's a little nice formula for them, and from it follows at once that a natural has an odd number of divisors iff it is a square.

Tonio