How many positive integers $\le 462$ are relatively prime to $462$?

Question

How many positive integers less than or equal to $462$ are relatively prime to $462$?

My Approach Well my approach is basically that we find $|A \cup B|$ where:

• $A = \{\text{all prime numbers} \le 462\}$
• $B = \{\text{every number which isn't a factor of } 462\}$

I just don't know how to calculate this so it is not an efficient method so please answer with a more efficient method. Thank you!

Answer 1

$462 = 2\times3\times7\times11$

let A be the set of integers from 1 to 462 divisible by 2

let B be the set of integers from 1 to 462 divisible by 3

let C be the set of integers from 1 to 462 divisible by 7

let D be the set of integers from 1 to 462 divisible by 11

$A\cup B\cup C\cup D$ is the set of all integers from 1 to 462 that are NOT relatively prime to 462.

So your answer will be

$462 - n(A\cup B\cup C\cup D)$

So you have to get $n(A\cup B\cup C\cup D)$. (that's just the number of elements in the union)

The pattern to get the number of elements in a union is simple. Start with $n(A)+n(B)+n(C)+n(D)$ then subtract the number of elements in the intersection of each pair... then add the number of elements in the intersection of each triple... then subtract the number of elements in the intersection of each quadruple. Described better here:

https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

$n(A) = 462/2 = 231$... calculate all the others the same way.

Can you take it from here?

Totient function is an easier method, but I don't know if you're allowed to use that.

Answer 2

HINT: Euler's Totient function $\phi$ is multiplicative. In other words, if we have two positive integers $a$ and $b$ with $\gcd(a,b) = 1$, then $\phi(ab) = \phi(a)\phi(b)$. So, you can use prime factorization of $462$ to divide and conquer the problem.