# Number theory challenge

• Mar 21st 2008, 08:37 PM
delicate_tears
Number theory challenge
What's is the best strategy to use to solve this problem?

How many positive integers less than 72 have the property that the highest common factor of the number and 72.

I think I heard something about reducing 72 into its lowest prime numbers~ and then list the numbers less than 72 that do not have 2 or 3 as factors? But wouldn't that take a long time? Is there another efficient strategy?
• Mar 22nd 2008, 01:20 AM
CaptainBlack
Quote:

Originally Posted by delicate_tears
What's is the best strategy to use to solve this problem?

How many positive integers less than 72 have the property that the highest common factor of the number and 72.

As it stands that is not a question

Quote:

I think I heard something about reducing 72 into its lowest prime numbers~ and then list the numbers less than 72 that do not have 2 or 3 as factors? But wouldn't that take a long time?
No.

Quote:

Is there another efficient strategy?
Probably

If N is this largest common factor, then for every K which has no factor in common with 72
hcf(NK,72)=N

RonL