How Many Integers Are Relatively Prime to a Given Number?

“Numbers of relatively primes” most commonly means: How many integers from 1 through a given positive integer $n$ have greatest common divisor 1 with $n$? The answer is Euler’s totient function, written $\varphi(n)$. The same inclusion–exclusion idea also counts integers relatively prime to $n$ in a longer interval, such as $1$ through $N$.

Count integers from 1 through n

An integer $a$ is relatively prime to $n$ when $\gcd(a,n)=1$. Factor $n$ into primes, keeping only the distinct primes:

$$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}.$$

A number from 1 through $n$ fails to be relatively prime to $n$ exactly when it is divisible by at least one of $p_1,\ldots,p_k$. Inclusion–exclusion counts the numbers that avoid all of these prime divisors. The result is

$$\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right).$$

Equivalently, multiply $n$ by one factor $1-1/p$ for each distinct prime divisor $p$ of $n. The exponents in the prime factorization do not affect which primes must be excluded.

For $n=1$, the usual convention is $\varphi(1)=1$: the only integer in the range 1 through 1 is 1, and $\gcd(1,1)=1$.

Worked example: count numbers relatively prime to 30

The distinct prime factors of 30 are 2, 3, and 5. Therefore,

$$\begin{aligned} \varphi(30) &=30\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)\\ &=30\cdot\frac12\cdot\frac23\cdot\frac45\\ &=8. \end{aligned}$$

So there are 8 integers from 1 through 30 relatively prime to 30. Listing them confirms the count:

$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29.$$

Every other integer in that range is divisible by 2, 3, or 5, so it shares a prime factor with 30.

Count up to a different endpoint

If you want the number of integers from 1 through $N$ relatively prime to $n$, where $N$ is not necessarily $n$, use inclusion–exclusion with floor functions. Let $p_1,\ldots,p_k$ be the distinct prime divisors of $n$. For a positive integer $d$, the number of multiples of $d$ from 1 through $N$ is $\lfloor N/d\rfloor$.

Start with all $N$ integers. Subtract the multiples of each prime divisor, add back the multiples of each pair of prime divisors, subtract the multiples of each triple, and continue with alternating signs. For example, if $n$ has three distinct prime divisors $p,q,r$, the count is

$$N-\left\lfloor\frac{N}{p}\right\rfloor-\left\lfloor\frac{N}{q}\right\rfloor-\left\lfloor\frac{N}{r}\right\rfloor +\left\lfloor\frac{N}{pq}\right\rfloor+\left\lfloor\frac{N}{pr}\right\rfloor+\left\lfloor\frac{N}{qr}\right\rfloor -\left\lfloor\frac{N}{pqr}\right\rfloor.$$

For $n=30$ and $N=100$, this gives

$$\begin{aligned} 100-&\left\lfloor\frac{100}{2}\right\rfloor-\left\lfloor\frac{100}{3}\right\rfloor-\left\lfloor\frac{100}{5}\right\rfloor\\ &+\left\lfloor\frac{100}{6}\right\rfloor+\left\lfloor\frac{100}{10}\right\rfloor+\left\lfloor\frac{100}{15}\right\rfloor-\left\lfloor\frac{100}{30}\right\rfloor\\ &=100-50-33-20+16+10+6-3\\ &=26. \end{aligned}$$

Thus 26 integers from 1 through 100 are relatively prime to 30. The floor functions matter: for example, 33 integers in that range are divisible by 3, not 100/3 integers.

Why the formula works

For each prime divisor $p$ of $n$, the fraction $1/p$ of the integers in a full block of length $n$ are multiples of $p$. Removing those integers for every prime factor would subtract some numbers more than once. Inclusion–exclusion corrects this: numbers divisible by two selected primes are added back, those divisible by three are subtracted again, and so on. In a full block of length $n$, the resulting proportions multiply to $\prod(1-1/p)$, yielding the totient formula.

The same reasoning works for any endpoint $N$, but a partial block generally does not contain exact fractions such as $N/p$ of the multiples. That is why the general count uses floors.

Common mistakes

• Using repeated prime factors: For $n=12=2^2\cdot3$, use the primes 2 and 3 once each. The formula gives $\varphi(12)=12(1-1/2)(1-1/3)=4$.
• Counting only numbers less than $n$ without saying so: The standard definition counts $1\leq a\leq n$. For $n>1$, including $n$ does not change the count, since $\gcd(n,n)=n>1$.
• Confusing “relatively prime to $n$” with “prime”: A number can be composite and still be relatively prime to $n$. For example, 49 is relatively prime to 30.
• Using the totient formula for the wrong endpoint: $\varphi(n)$ counts candidates from 1 through $n$. For a different endpoint, use inclusion–exclusion with floors.