# Number of positive integers less than 550 and relatively prime to 550

• Jul 18th 2010, 02:49 PM
dwsmith
Number of positive integers less than 550 and relatively prime to 550
$550=2*5^2*11$

Is there an efficient way to do this without just multiplying all the combinations of the canonical decomposition?
• Jul 18th 2010, 02:55 PM
undefined
Quote:

Originally Posted by dwsmith
$550=2*5^2*11$

Is there an efficient way to do this without just multiplying all the combinations of the canonical decomposition?

Do you mean you want something more efficient than this?

$\displaystyle \varphi(550)= 550 \cdot \prod_{p|550} \left( 1-\frac{1}{p} \right) = 550\left( 1-\frac{1}{2} \right)\left( 1-\frac{1}{5} \right)\left( 1-\frac{1}{11} \right) = 200$

If you're writing a program, then you can do a sieve. I don't know what else.
• Jul 18th 2010, 02:57 PM
dwsmith
I knew the phi function but I couldn't remember what it did. Thanks. I feel dumb now.