1. ## Euler Function phi(n)

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

2. 1. I think you may have meant to say : $\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 $n = 12$ and we have a class of numbers $C_{d}$ where $C_{d}$ holds any number less than $n$ that has its highest divisor as $d$. Then we have a set of classes:
$C_{1} = \{1, 5, 7, 11\}$
$C_{2} = \{2, 10\}$
$C_{3} = \{3, 9\}$
$C_{4} = \{4, 8\}$
$C_{6} = \{6\}$
$C_{12} = \{12\}$

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

From here it is a simple matter.

We just proved that $\sum_{d|n}{phi(d/n)} = n$ and if you work it out manually with a small number like $n = 12$ you will find that $\sum_{d|n}{phi(d/n)} = \sum_{d|n}{phi(n)}$ and with that we have proved $\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 $\phi(2n) = \phi(n)$ works for even numbers as well. If $n = 2^1$, then we can use the equation $\phi(p^{e}) = p^{e-1}(p-1)$ where p is a prime and e is its power. If we work it out with $n = 2$ (a prime) then $\phi(4) = 2^0(2-1) = 2$ while $\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.

3. Is the statement $\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?

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

5. Originally Posted by 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
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!

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

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

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

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

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

7. Originally Posted by chiph588@
1.) This proof comes from Apostol's book on analytic number theory.

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

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

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

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

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

8. Originally Posted by 1337h4x

-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 $n$ is odd, then $\phi(2n) = \phi(2)\phi(n)\ldots$

What are these problems for?

9. Originally Posted by chiph588@
3.) As far as I know, there isn't a proof or methodology...

2.) If $n$ is odd, then $\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).

10. Originally Posted by 1337h4x
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 $n$ is odd, $(2,n)=1$. Thus $\phi(2n) = \phi(2)\phi(n) = \phi(n)$ because $\phi(2)=1$.

11. Originally Posted by chiph588@
Since $n$ is odd, $(2,n)=1$. Thus $\phi(2n) = \phi(2)\phi(n) = \phi(n)$ because $\phi(2)=1$.
I'm sorry, I'm just not seeing how you're connecting the dots here.

If you could give the explicit example of how your relationship applies to the number 1729 that would greatly help.

Also, is there any sort of method to the madness for how you got that other number? Where did you find it from?

12. Originally Posted by 1337h4x
I'm sorry, I'm just not seeing how you're connecting the dots here.

If you could give the explicit example of how your relationship applies to the number 1729 that would greatly help.

Also, is there any sort of method to the madness for how you got that other number? Where did you find it from?
for the first part if you're still not seeing it: $\phi(2)$ is the same as 1. So $\phi(2)\phi(n) = \phi(n)$ and this works for all odd numbers because $(2, n) = 1$. That's about as simple as it gets.

13. Originally Posted by BBAmp
for the first part if you're still not seeing it: $\phi(2)$ is the same as 1. So $\phi(2)\phi(n) = \phi(n)$ and this works for all odd numbers because $(2, n) = 1$. That's about as simple as it gets.
So how do you prove that if n is even that phi(2n)=2*phi(n) ?

14. suppose $(2, n) = 2$ or in other words $n$ is an even number. Also remember our original equation for even numbers that we are looking to prove ( $\phi(2n)= \phi(2)\phi(n) = 2\phi(n)$)

The definition of $\phi(n)$ is as follows:

$\phi(n) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})$

Using this definition if you take $\phi(n/2)$ you get $\phi(n/2) = n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})$

if you multiply $\phi(n/2)$ by $2$ you get $2\phi(n/2) = 2(n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k}))$ which by simple cancellation of the $2$ becomes

$2\phi(n/2) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k}) = \phi(n)$.

That proves that $\phi(2n)= \phi(2)\phi(n) = 2\phi(n)$

I think I may have run into an error and I might be wrong. I don't have time at the moment so if you can spot it please point it out and I will get back to this later.

15. Originally Posted by BBAmp
suppose $(2, n) = 2$ or in other words $n$ is an even number. Also remember our original equation for even numbers that we are looking to prove ( $\phi(2n)= \phi(2)\phi(n) = 2\phi(n)$)

The definition of $\phi(n)$ is as follows:

$\phi(n) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})$

Using this definition if you take $\phi(n/2)$ you get $\phi(n/2) = n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k})$

if you multiply $\phi(n/2)$ by $2$ you get $2\phi(n/2) = 2(n/2(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k}))$ which by simple cancellation of the $2$ becomes

$2\phi(n/2) = n(1-1/p_{1})(1-1/p_{2})...(1-1/p_{k}) = \phi(n)$.

That proves that $\phi(2n)= \phi(2)\phi(n) = 2\phi(n)$

I think I may have run into an error and I might be wrong. I don't have time at the moment so if you can spot it please point it out and I will get back to this later.
did anyone else find an error? I was just confused about why you used n/2 as your example and how you at all used the fact that (2,n)=2 ...

Page 1 of 2 12 Last

,

,

,

,

,

,

,

,

,

# phi(2n)=phi(n) prove it

Click on a term to search for related topics.