- Thread starter
- #1

- Apr 14, 2013

- 4,925

I am looking at an exercise and I got stuck...

$n\epsilon \mathbb{N},n>1$

$φ(n)=|\{1 \leq k \leq n :$ the greatest common divisor of $k$ and $n$ is $1\}|$

I am asked to find $φ(n)$,but I don't know how...

- Thread starter mathmari
- Start date

- Thread starter
- #1

- Apr 14, 2013

- 4,925

I am looking at an exercise and I got stuck...

$n\epsilon \mathbb{N},n>1$

$φ(n)=|\{1 \leq k \leq n :$ the greatest common divisor of $k$ and $n$ is $1\}|$

I am asked to find $φ(n)$,but I don't know how...

- Admin
- #2

- Mar 5, 2012

- 9,774

It has a name and is called Euler's totient function.

I am looking at an exercise and I got stuck...

$n\epsilon \mathbb{N},n>1$

$φ(n)=|\{1 \leq k \leq n :$ the greatest common divisor of $k$ and $n$ is $1\}|$

I am asked to find $φ(n)$,but I don't know how...

Suppose $n=7$ which is a prime number.

How many numbers $k$ are there that have a greatest common divisor of $1$?

Or in other words, that are

Btw, I have moved your thread to Number Theory, which is a better match.

- Mar 10, 2012

- 835

In my opinion this isn't really an

I am looking at an exercise and I got stuck...

$n\epsilon \mathbb{N},n>1$

$φ(n)=|\{1 \leq k \leq n :$ the greatest common divisor of $k$ and $n$ is $1\}|$

I am asked to find $φ(n)$,but I don't know how...

Anyway.

1. Try to show that $\phi(mn)=\phi(m)\phi(n)$ whenever $m$ and $n$ are relatively prime.

2. Find $\phi(p^k)$ for prime a prime $p$ and an integer $k$. (This is easy)

From here you easily get a formula.

- Thread starter
- #4

- Apr 14, 2013

- 4,925

For $n=7$ there are $6$ numbers that have a greatest common divisor of $1$.It has a name and is called Euler's totient function.

Suppose $n=7$ which is a prime number.

How many numbers $k$ are there that have a greatest common divisor of $1$?

Or in other words, that arerelatively prime, orco-prime.

So from the Euler's totient function,we have $φ(7)=7(1-\frac{1}{7})=7\frac{6}{7}=6$.

Ok!Btw, I have moved your thread to Number Theory, which is a better match.

- - - Updated - - -

How can I show the first one,that $\phi(mn)=\phi(m)\phi(n)$ ?In my opinion this isn't really anexercise.Its more like aproblem.

Anyway.

1. Try to show that $\phi(mn)=\phi(m)\phi(n)$ whenever $m$ and $n$ are relatively prime.

2. Find $\phi(p^k)$ for prime a prime $p$ and an integer $k$. (This is easy)

From here you easily get a formula.

- Admin
- #5

- Mar 5, 2012

- 9,774

Good.For $n=7$ there are $6$ numbers that have a greatest common divisor of $1$.

So from the Euler's totient function,we have $φ(7)=7(1-\frac{1}{7})=7\frac{6}{7}=6$.

You may notice that if $n$ is a prime, there are $n-1$ numbers that are relatively prime.

Btw, with Euler's totient function, you already have an answer...

Well, I'll assume for now that you have to find the answer yourself without Euler's totient function.

How many co-primes if $n=7^3$?

- Mar 22, 2013

- 573

Interesting exercise, I would say. This is indeed the totient function of Euler, as said by I like Serena. caffeinmachine gives almost every hint possible, but still, I thought I would give you a few pointers :

Note that this is a multiplicative function, i.e., $\varphi(mn) = \varphi(m)\varphi(n)$ for coprime pair $(m, n)$. This is easy to show from the definition.

Now what you need is what happens for $(m, n) \neq 1$. Obviously, a factor of $c_k \geq 1$ multiplies up. Conclude that $c_k = \frac{(m, n)}{\varphi((m, n))}$ by inclusion-exclusion "like" idea.

You need a further important result to come up with a generalized result, i.e, the fundamental theorem of arithmetic. After some calculations, conclude

$$\varphi(n) = \prod_{p|n} \left (1 - \frac{1}{p}\right)$$

Note that this is a multiplicative function, i.e., $\varphi(mn) = \varphi(m)\varphi(n)$ for coprime pair $(m, n)$. This is easy to show from the definition.

Now what you need is what happens for $(m, n) \neq 1$. Obviously, a factor of $c_k \geq 1$ multiplies up. Conclude that $c_k = \frac{(m, n)}{\varphi((m, n))}$ by inclusion-exclusion "like" idea.

You need a further important result to come up with a generalized result, i.e, the fundamental theorem of arithmetic. After some calculations, conclude

$$\varphi(n) = \prod_{p|n} \left (1 - \frac{1}{p}\right)$$

Last edited by a moderator:

- Feb 15, 2012

- 1,967

Let's ask an easier question, first:For $n=7$ there are $6$ numbers that have a greatest common divisor of $1$.

So from the Euler's totient function,we have $φ(7)=7(1-\frac{1}{7})=7\frac{6}{7}=6$.

Ok!

- - - Updated - - -

How can I show the first one,that $\phi(mn)=\phi(m)\phi(n)$ ?

Suppose $p$ and $q$ are primes. Clearly, EVERY positive integer less than $p$ is co-prime to $p$ (that's why we call them primes, right?). A similar assertion hold for $q$, so:

$\phi(p) = p-1$

$\phi(q) = q-1$.

Now, let's consider how many numbers share a common divisor other than 1 with the product $pq$.

Well, clearly, all the multiples:

$p,2p,3p,\dots$ do, and likewise with $q,2q,3q,\dots$.

It's pretty clear that these are all there are for integers $< pq$. Well we can count how many of these there are:

$p,2p,\dots,(q-1)p$ (the next multiple of $p$ is $pq$) for multiples of $p$, and:

$q,2q,\dots,(p-1)q$ for multiples of $q$.

So we have $q-1$ multiples of $p$ we have to "subtract out" from the $pq - 1$ positive integers less than $pq$, and $p-1$ multiples of $q$ to subtract out, as well.

So: $\phi(pq) = pq - 1 - (p-1) - (q-1) = pq - 1 - p + 1 - q + 1 = pq - p - q + 1$

$= pq - (p+q) + 1 = (p - 1)(q - 1) = \phi(p)\phi(q)$.

Now, it's actually easier to show next that if: $n = p^k$ then:

$\phi(n) = p^{k-1}(p -1)$

Suppose $\text{gcd}(m,p^k) = d > 1$. Clearly $d$ is of the form $p^t$ for some $0 < t \leq k$, and $p$ divides every single one of these.

On the other hand, it should be clear that every multiple of $p$ up to (but not including) $p^{k-1}p$ has such a common factor, and we can count these multiples of $p$:

$p,2p,\dots,p^2,(p^2+1)p,\dots,p^3,\dots,(p^{k-1} - 1)p$, so there are:

$p^{k-1} - 1$ integers less than $p^k$ that are NOT co-prime to $p^k$, and this is all of them.

Hence:

$\phi(p^k) = p^k - 1 - (p^{k-1} - 1) = p^k - p^{k-1} = p^{k-1}(p - 1)$.

So, what is there left to show? Well, we haven't covered every possible integer, yet.

Use what I have above, to show that:

$\phi(p^kq^m) = \phi(p^k)\phi(q^m)$ (just two prime factors).

(Hint: if $n = p^kq^m$ show that if $\text{gcd}(r,n) \neq 1$, either $p|r$ or $q|r$. Count the multiples of $p$ and the multiples of $q$, and subtract the ones you've "double-counted" (the multiples of $pq$)).

Now use induction on the number of primes in any factorization of $n$ to get a general formula (use a similar "counting trick").

**********

On a slightly different tack, it turns out this result is actually equivalent to the Chinese Remainder Theorem, which may be more accessible to you (depending on your mathematical background), often stated in the form:

$U(\Bbb Z_m \times \Bbb Z_n) \cong U(\Bbb Z_m) \times U(\Bbb Z_n)$

**********

Small correction:

The actual formula is:

$\displaystyle \phi(n) = n\prod_{p|n} \left(1 - \frac{1}{p}\right)$.

This seems a lot less mysterious when you realize:

$p^{k-1}(p-1) = p^k\left(1 - \dfrac{1}{p}\right)$

so you put all the prime factors of $n$ outside the $\prod$ sign (together, they multiply up to...$n$), and all the:

$\left(1 - \dfrac{1}{p}\right)$

factors inside the "giant product".

- Admin
- #8

- Mar 5, 2012

- 9,774

Since it did trigger responses from other members, it seemed best to me to create a dedicated thread for it.