1
$\begingroup$

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$?

$\endgroup$
  • 7
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Mar 4 '14 at 6:15
1
$\begingroup$

$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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.