# Find all integers less than $m$ that are relatively prime to it

Find all integers $n$ between $0\le n < m$ that are relatively prime to $m$, for $m = 4,5,9, 26$. We denote the number of integers $n$ which fulfill the condition by $\phi (m)$, e.g. $\phi (3) = 2$. This function is called "Euler's phi function". What is $\phi (m)$ for $m =4,5,9,26$?

• The instructions seem clear enough to be carried out. First problem, $m=4$. We are to look at $0,1,2,3$, identify which ones are relatively prime to $4$, and count them. That count will be $\varphi(4)$. Then move on to $m=5$. – André Nicolas Mar 4 '14 at 6:15

## 2 Answers

$m$ and $n$ relatively prime is equivalent to $gcd(m,n)=1$. Consider the prime factorizations: $4=2^2$, $5=5^1$, $9=3^2$ and $26=2^*13$

Instead of providing a solution i'll suggest you to consider looking and proving the properties of the totient function. (And so you'll be able to finish a wider class of excercise of this kind)

You are interested in multiplicativity and behaviour of the function with power of a prime.