relatively prime to 165, and less than or equal to 165

[calchere]

How many integers less than or equal to 165 are relative prime to 165?

So, the prime factorization is: 3x5x11
For small numbers, like 30, i could just check each number, 1-30, to see if it had a common prime factor.
But this number is very large, and i am guessing there is an easier and quicker way to do this.

By the way, this is a linear algebra problem.

Thanks.

 

[TchrWill]

Re: relatively prime

How many integers less than or equal to 165 are relative prime to 165?

The prime factorization of 165 is 3(5)11

The total number of factors/divisors is f(165) = (1 + 1)(1 + 1)(1 + 1) = 8, namely 1, 3, 5, 11, 15, 33, 55 and 165.

All the numbers other than those evenly divisible by these numbers are relatively prime to 165.

 

[pka]

Re: relatively prime

Using the floor function \(\displaystyle \left\lfloor {\frac{{165}}{n}} \right\rfloor\) gives the number of integers form 1 to 165 are divisible by n. Example \(\displaystyle \left\lfloor {\frac{{165}}{{15}}} \right\rfloor = 11\) means the 11 positive integers less or equal to 165 are divisible by 15.

The number of integers form 1 to 165 are divisible by 3, 5 or 11 is given by:
\(\displaystyle \left\lfloor {\frac{{165}}{3}} \right\rfloor + \left\lfloor {\frac{{165}}{5}} \right\rfloor + \left\lfloor \frac{{165}}{{11}}} \right\rfloor - \left\lfloor {\frac{{165}}{{15}}} \right\rfloor - \left\lfloor \frac{{165}}{{33}}} \right\rfloor - \left\lfloor {\frac{{165}}{{55}}} \right\rfloor + \left\lfloor {\frac{{165}}{{165}}} \right\rfloor\).
Subtract that number from 165 and that is the number of integers that are relatively prime with 165.

 

[stapel]

How many integers less than or equal to 165 are relative prime to 165?

So, the prime factorization is: 3x5x11...

So any number with a factor of 3, 5, or 11 will not be relatively prime to 165, since that number and 165 will share a factor. How many numbers are multiples of 3 and are less than 165? (Hint: Divide 165 - 3 by 3.) How many are multiples of 5? How many are multiples of 11?

Obviously 165 is not relatively prime to 165, so that's one number "less than or equal to 165" that doesn't count. Add "1" (for 165) to the counts for the numbers of multiples of 3, 5, and 11. This gives you a count of all of the numbers which are not relatively prime to 165.

How many whole numbers (or positive integers; they can't meant just "integers") are there between 1 and 165? How many are not relatively prime? So how many are left that are?

For further information, try here:

. . . . .Cut the Knot: Euler Function and Theorem

. . . . ."Yahoo Answers" discussion with helpful example

Hope that helps!

Eliz.

 

[calchere]

Re: relatively prime

Ok, so i get:
55+33+15-11-5-3-1=83
165-83=82

So, 82 positive integers are relatively prime to 165.

Thank you for the help.

 

[pka]

Re: relatively prime

Ok, so i get:
55+33+15-11-5-3+1=85
165-85=80
So, 80 positive integers are relatively prime to 165.

You have some minor errors in the arithmetic.

 

[galactus]

Re: relatively prime

By the Euler Product, \(\displaystyle {\phi}(n)\)

\(\displaystyle {\phi}(n)=n\cdot{\Pi}_{p|n}\left(1-\frac{1}{p}\right)\)

The prime factorization of 165 is \(\displaystyle 3\cdot{5}\cdot{11}\)

Therefore, the number of integers relatively prime to 165 is given by:

\(\displaystyle 165(1-\frac{1}{3})(1-\frac{1}{5})(1-\frac{1}{11})=\boxed{80}\)