Number Theory Find the cardinality of a set

[mathmari]

Hey!
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...

 

[Klaas van Aarsen]

Hey!
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...

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 are relatively prime, or co-prime.


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

 

[caffeinemachine]

Hey!
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...

In my opinion this isn't really an exercise. Its more like a problem.

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.

 

[mathmari]

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 are relatively prime, or co-prime.

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

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

Ok!

- - - Updated - - -

In my opinion this isn't really an exercise. Its more like a problem.

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.

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

 

[Klaas van Aarsen]

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

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

 

[mathbalarka]

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

 

[Deveno]

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

Let's ask an easier question, first:

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".

 

[Klaas van Aarsen]

Moderator's note: I have taken the liberty to split the second part of Mathbalarka's post into a separate thread, as it doesn't really address the problem statement in the OP.
Since it did trigger responses from other members, it seemed best to me to create a dedicated thread for it.