# Euler Function phi(n)

#### 1337h4x

Hello All,

I am reading about the Euler Function phi(n), which my book defines counts the number of positive integers less then or equal to n, which are relatively prime. The book has a couple examples of how this works, but I do have some questions about a couple of the examples:

1. $$\displaystyle \sum_{d|n}^{} phi(d)$$ can be evaluated and proven correct. Can someone explain this?

2. Analyzing n:
If n is odd, then phi(2n)=phi(n)
If n is even, then phi(2n)=2*phi(n).
How can this be proven?

3. An n exists where phi(n)=phi(n+1)=phi(n+2). What is the n?
There are a few guidelines to this one, it says try taking phi(n)=2592. Then note that phi(2n)=phi(n) when n is odd. Then note that phi(p)=p-1 for a prime 'p'.

Any help is appreciated!

#### BBAmp

1. I think you may have meant to say : $$\displaystyle \sum_{d|n}{phi(n)} = n$$ in which case you can work it out like so - a method by Gauss that I learned from my book - and I'll go through it step by step since I am new to this myself:

Suppose $$\displaystyle n = 12$$ and we have a class of numbers $$\displaystyle C_{d}$$ where $$\displaystyle C_{d}$$ holds any number less than $$\displaystyle n$$ that has its highest divisor as $$\displaystyle d$$. Then we have a set of classes:
$$\displaystyle C_{1} = \{1, 5, 7, 11\}$$
$$\displaystyle C_{2} = \{2, 10\}$$
$$\displaystyle C_{3} = \{3, 9\}$$
$$\displaystyle C_{4} = \{4, 8\}$$
$$\displaystyle C_{6} = \{6\}$$
$$\displaystyle C_{12} = \{12\}$$

A number m only exists in $$\displaystyle C_{d}$$ if $$\displaystyle (m, n) = d$$. Further, $$\displaystyle (m/d, n/d) = 1$$ so a number m only exists in $$\displaystyle C_{d}$$ if $$\displaystyle m/d$$ and $$\displaystyle n/d$$ are relatively prime. By definition the number of integers less than $$\displaystyle n/d$$ and relatively prime to $$\displaystyle n/d$$ is $$\displaystyle \phi(n/d)$$ so the number of elements in $$\displaystyle C_{d}$$ is $$\displaystyle \phi(n/d)$$.

From here it is a simple matter.

We just proved that $$\displaystyle \sum_{d|n}{phi(d/n)} = n$$ and if you work it out manually with a small number like $$\displaystyle n = 12$$ you will find that $$\displaystyle \sum_{d|n}{phi(d/n)} = \sum_{d|n}{phi(n)}$$ and with that we have proved $$\displaystyle \sum_{d|n}{phi(n)} = n$$

For the record I relied quite heavily on my book for much of the above so I cannot take credit for this work.

2. I know there is a much more complete way of proving this, but at the moment I can only think of a proof by contradiction:

Lets suppose $$\displaystyle \phi(2n) = \phi(n)$$ works for even numbers as well. If $$\displaystyle n = 2^1$$, then we can use the equation $$\displaystyle \phi(p^{e}) = p^{e-1}(p-1)$$ where p is a prime and e is its power. If we work it out with $$\displaystyle n = 2$$ (a prime) then $$\displaystyle \phi(4) = 2^0(2-1) = 2$$ while $$\displaystyle \phi(2) = 1$$. We have reached a contradiction and we at least know for the even number 2 this does not work. The only problem is I do not know how to extend this to all even numbers. This is a very weak proof and I would like to see someone else write one better.

3. I can't figure this one out either.

#### 1337h4x

Is the statement $$\displaystyle \sum_{d|n}{phi(n)} = n$$ true? My book just says "it can be evaluated", it doesn't say what it is equal too.

Also, can anyone confirm his results?

Does anyone also have an idea of approaching my 3rd point?

#### BBAmp

If your book just says it can be evaluated then I believe I have shown that it in fact can though there may be a more direct proof showing that it can be evaluated. I hope my example helped (Nod)

#### 1337h4x

If your book just says it can be evaluated then I believe I have shown that it in fact can though there may be a more direct proof showing that it can be evaluated. I hope my example helped (Nod)
Yes, I just hope someone can confirm your 2nd point result and someone can chime in on my 3rd point question. Thank you for all your help thus far! Let's keep rolling with this!

#### [email protected]

MHF Hall of Honor
1.) This proof comes from Apostol's book on analytic number theory.

Let $$\displaystyle N=\{1,2,3,\ldots,n\}$$. For each divisor $$\displaystyle d$$ of $$\displaystyle n$$ define $$\displaystyle S(d) = \{k \; | \; (k,n)=d, \; 1\leq k \leq n \}$$ i.e $$\displaystyle S(d)$$ contains all elements of $$\displaystyle N$$ which have gcd $$\displaystyle d$$ with $$\displaystyle n$$. The sets $$\displaystyle S(d)$$ form a disjoint collection whose union is $$\displaystyle N$$. Thus if $$\displaystyle f(d)$$ denotes the number of integers in $$\displaystyle S(d)$$, we have $$\displaystyle \sum_{d\mid n}f(d) = n$$.

But $$\displaystyle (k,n)=d \iff (k/d,n/d)=1$$ and $$\displaystyle 1\leq k \leq n \iff 1\leq k/d \leq n/d$$. So if we let $$\displaystyle q=k/d$$ there is a one-to-one correspondence between the elements in $$\displaystyle S(d)$$ and those integers $$\displaystyle q$$ satisfying $$\displaystyle 1\leq q \leq n/d$$ and $$\displaystyle (q,n/d)=1$$. The number of such $$\displaystyle q$$ is $$\displaystyle \phi(n/d)$$. Thus $$\displaystyle f(d) = \phi(n/d)$$.

Therefore $$\displaystyle n = \sum_{d\mid n} \phi(n/d) = \sum_{d\mid n} \phi(d)$$.

3.) The only number known that satisfies this property is $$\displaystyle n=5186$$.

#### 1337h4x

1.) This proof comes from Apostol's book on analytic number theory.

Let $$\displaystyle N=\{1,2,3,\ldots,n\}$$. For each divisor $$\displaystyle d$$ of $$\displaystyle n$$ define $$\displaystyle S(d) = \{k \; | \; (k,n)=d, \; 1\leq k \leq n \}$$ i.e $$\displaystyle S(d)$$ contains all elements of $$\displaystyle N$$ which have gcd $$\displaystyle d$$ with $$\displaystyle n$$. The sets $$\displaystyle S(d)$$ form a disjoint collection whose union is $$\displaystyle N$$. Thus if $$\displaystyle f(d)$$ denotes the number of integers in $$\displaystyle S(d)$$, we have $$\displaystyle \sum_{d\mid n}f(d) = n$$.

But $$\displaystyle (k,n)=d \iff (k/d,n/d)=1$$ and $$\displaystyle 1\leq k \leq n \iff 1\leq k/d \leq n/d$$. So if we let $$\displaystyle q=k/d$$ there is a one-to-one correspondence between the elements in $$\displaystyle S(d)$$ and those integers $$\displaystyle q$$ satisfying $$\displaystyle 1\leq q \leq n/d$$ and $$\displaystyle (q,n/d)=1$$. The number of such $$\displaystyle q$$ is $$\displaystyle \phi(n/d)$$. Thus $$\displaystyle f(d) = \phi(n/d)$$.

Therefore $$\displaystyle n = \sum_{d\mid n} \phi(n/d) = \sum_{d\mid n} \phi(d)$$.

3.) The only number known that satisfies this property is $$\displaystyle n=5186$$.
Thank you! A few comments:

-Do you know how to prove the second point I listed in my original post?
-How did you come to n=5186 ? Is there some sort of proof or methodology?

#### [email protected]

MHF Hall of Honor
Thank you! A few comments:

-Do you know how to prove the second point I listed in my original post?
-How did you come to n=5186 ? Is there some sort of proof or methodology?
3.) As far as I know, there isn't a proof or methodology...

2.) If $$\displaystyle n$$ is odd, then $$\displaystyle \phi(2n) = \phi(2)\phi(n)\ldots$$

What are these problems for?

#### 1337h4x

3.) As far as I know, there isn't a proof or methodology...

2.) If $$\displaystyle n$$ is odd, then $$\displaystyle \phi(2n) = \phi(2)\phi(n)\ldots$$

What are these problems for?
3. So where did you come up with the number?

2. What is your relation pointing out? I'm missing the link and how it relates to 1729.

These problems are "suggested exercises" and examples that my book gives. Point 2 came from my book stating, "There exists a set of numbers that are pseudoprimes, e.g. 1729" , and I didn't understand why. I casually am trying to get back into mathematical studying after being out of it for so long. I figured Number Theory was a good place to start, followed by combinatorics (which I'll get into once I finish getting through this book).

#### [email protected]

MHF Hall of Honor
3. So where did you come up with the number?

2. What is your relation pointing out? I'm missing the link and how it relates to 1729.
Since $$\displaystyle n$$ is odd, $$\displaystyle (2,n)=1$$. Thus $$\displaystyle \phi(2n) = \phi(2)\phi(n) = \phi(n)$$ because $$\displaystyle \phi(2)=1$$.