Totient Function and phi(n)=phi(2n) for odd n

  • Thread starter timo1023
  • Start date
  • Tags
    Function
In summary: Even numbers are defined as numbers divisible by 2. This is a basic concept in mathematics.As for your statement about ϕ(3m), that is not true. For example, ϕ(3*5)=8 but ϕ(5)=4.
  • #1
timo1023
8
0
Hello,

Last year in number theory I discovered something with Euler's Totient Function that I couldn't explain. I asked my professor and he couldn't figure it out either. Here is what I discovered:

As a premise, it should be clear that phi(n)==phi(2n) where n is an odd, positive, integer. Using the formula for Euler's totient function, this is clear. However, looking at the numbers, it becomes more complex. For example, let n = 9. We know that phi(9)=phi(18)=6.

So we have the pos. integers from 1 to 9 ( n in red, coprime integers in blue, noncoprime integers in orange). Note that there are 4 primes in this range (2,3,5,7):

[itex]\definecolor{orange}{rgb}{1,0.5,0} {\color{blue}1}, {\color{blue}2}, {\color{orange}3}, {\color{blue}4}, {\color{blue}5}, {\color{orange}6}, {\color{blue}7}, {\color{blue}8}, {\color{red}9} [/itex]

Next, the integers from 1 to 18 for n=18. Note there are only 3 new primes from 9-18

[itex]\definecolor{orange}{rgb}{1,0.5,0} {\color{blue}1}, {\color{orange}2}, {\color{orange}3}, {\color{orange}4}, {\color{blue}5}, {\color{orange}6}, {\color{blue}7}, {\color{orange}8}, {\color{orange}9}, {\color{orange}10}, \color{blue}11}, \color{orange}12}, \color{blue}13}, \color{orange}14}, \color{orange}15}, \color{orange}16}, \color{blue}17}, \color{red}18}[/itex]

I'm having a hard time phrasing this, but I think what I mean to say is this: How can the phi function know to compensate for the number of prime numbers between n and 2n? Wouldn't this be related to the density of primes? Also, could this be used to prove that there exist infinite prime numbers?

I'm sorry If my wording is hard to understand. Once I gain some more understanding, I would like to write it up properly and show it to my math teacher or something.

Thanks in advance.
 
Physics news on Phys.org
  • #2
That's interesting. I'll try to get something to get back to you with.
 
  • #3
timo1023 said:
Hello,

Last year in number theory I discovered something with Euler's Totient Function that I couldn't explain. I asked my professor and he couldn't figure it out either. Here is what I discovered:

As a premise, it should be clear that phi(n)==phi(2n) where n is an odd, positive, integer. Using the formula for Euler's totient function, this is clear. However, looking at the numbers, it becomes more complex. For example, let n = 9. We know that phi(9)=phi(18)=6.

So we have the pos. integers from 1 to 9 ( n in red, coprime integers in blue, noncoprime integers in orange). Note that there are 4 primes in this range (2,3,5,7):

[itex]\definecolor{orange}{rgb}{1,0.5,0} {\color{blue}1}, {\color{blue}2}, {\color{orange}3}, {\color{blue}4}, {\color{blue}5}, {\color{orange}6}, {\color{blue}7}, {\color{blue}8}, {\color{red}9} [/itex]

Next, the integers from 1 to 18 for n=18. Note there are only 3 new primes from 9-18

[itex]\definecolor{orange}{rgb}{1,0.5,0} {\color{blue}1}, {\color{orange}2}, {\color{orange}3}, {\color{orange}4}, {\color{blue}5}, {\color{orange}6}, {\color{blue}7}, {\color{orange}8}, {\color{orange}9}, {\color{orange}10}, \color{blue}11}, \color{orange}12}, \color{blue}13}, \color{orange}14}, \color{orange}15}, \color{orange}16}, \color{blue}17}, \color{red}18}[/itex]

I'm having a hard time phrasing this, but I think what I mean to say is this: How can the phi function know to compensate for the number of prime numbers between n and 2n? Wouldn't this be related to the density of primes? Also, could this be used to prove that there exist infinite prime numbers?

I'm sorry If my wording is hard to understand. Once I gain some more understanding, I would like to write it up properly and show it to my math teacher or something.

Thanks in advance.

This is no more than a comment. It is not an answer. Hence best phrased as a question.

You ask "How can the phi function know to compensate for the number of prime numbers between n and 2n?" But, does the data indicate that it really does that as opposed to compensating for the number of co-prime numbers between n and 2n?

Nothing more than a (hopefully) seminal question, but, I really would like it if you could give me your best shot at an answer.

DJ
 
  • #4
Upon further investigation, it seems as though you are right. Here is what I came up with (please forgive my lack of precision in stating x is a positive integer, etc.):

[itex]
\phi (2n)=\left{|}\{x|x\leq 2n-1\}-\{x|x \textrm{ is even}\} - \{i\cdot x | x \textrm{ odd}, x|n, i \textrm{ odd}\}\right{|}
[/itex]

So, for [itex]n=15[/itex], we have:

[itex]
\phi (30) = |\{1,\dots, 29\}-\{\textrm{evens}\}-\{3,9,15,21,27,5,25\}|
[/itex]
[itex]
\phi (30) = | 29-14-7 | = 8
[/itex]

As we already know, [itex]\phi (30)=\phi (15)=8[/itex], and thus this method works. So it would seem that it has nothing to do with the number of primes between 1 and 2n.

Please give me your thoughts.
 
  • #5
The formula for euler's function ϕ(n) is given by

ϕ(n) = n (1-1/p1) (1 – 1/p2) … (1 – 1/pk)
where n is prime factorized into p1a1p2a2...pkak and each pk is a prime.

Assume n is an odd number. None of the pk will be an even number. When n is multiplied by 2, the prime factorization of n will b (p1^a1)(p2^a2)...(pk^ak) * 2. The formula for ϕ(n) for 2n will be

ϕ(2n) = 2n ((1-1/p1) (1 – 1/p2) … (1 – 1/pk) (1 - ½) = n ((1-1/p1) (1 – 1/p2) … (1 – 1/pk)
which equals ϕ(n)

Assume n is an even number. Multiplying n by 2 will increase the power of 2 by 1.

ϕ(2n) = 2n ((1-1/p1) (1 – 1/p2) … (1 – 1/pk) = 2ϕ(n)

You're welcome.
 
  • #6
n=17 could be another interesting example. In the upper half of the coprimes to 34, you find not only new primes (19,23,29,31), but also powers of smaller primes (25,27) as well as other composite numbers (21,33).

As n gets bigger, the panorama gets only more varied.
 
  • #7
Doesn't ϕ(mn) = ϕ(m)ϕ(n)?

And doesn't ϕ(2) = 1?

What's the mystery?
 
  • #8
@Mensanator

ϕ(2m) = 2ϕ(m) ONLY IF m is even that's where's the mystery. And i think I did a pretty good job explaining it in post #5 if anyone is interested...
 
  • #9
squelchy451 said:
@Mensanator

ϕ(2m) = 2ϕ(m) ONLY IF m is even that's where's the mystery. And i think I did a pretty good job explaining it in post #5 if anyone is interested...

But what does "even" mean? It means no factors of two.

Have you noticed that ϕ(3m) is twice ϕ(m) if m is not divisible by 3?

Spooky!
 
  • #10
Mensanator said:
But what does "even" mean? It means no factors of two.

Are you serious?
 
  • #11
If the OP's question is why phi(2n) = phi(n) when n is odd, I think my explanation is clear enough,... see post #5.

please feel free to ask questions and don't say stuff like even numbers have no factor of two.
 
  • #12
squelchy451 said:
Are you serious?

Of course not. That was a brain fart.
 
  • #13
timo1023 said:
Also, could this be used to prove that there exist infinite prime numbers?

QUOTE]

Not alone it can't. Phi(n) gives no information about the number of prime factors of the numbers less than and coprime to n, just the quantity of them.

Phi(n) does give an upper bound on the number of primes. (Its a truly awful upper bound though, as n goes to infinity Phi(n) goes to c*n for some constant, c, I can't remember. The number of primes less than n goes to n/ln(n), a MUCH smaller number for large n).

But you could say that phi(n) is related to the infinite product (1-1/p1)*(1-1/p2)*(1-1/p3)...over all primes. This product is equal to the sum 1/k for every positive integer k. Since that sum diverges there must be an infinite number of primes (Euler).
 
  • #14
timo1023 said:
Also, could this be used to prove that there exist infinite prime numbers?

If there were finitely many primes, then phi(n) >= kn for some fixed positive k. If you know that there is an infinite sequence a_n with phi(a_n) < k a_n/log log a_n for some fixed positive k, then you could use this to show that there are infinitely many primes. But that's proving an easy result with a hard result.
 

1. What is the Totient Function?

The Totient Function, also known as Euler's Totient Function, is a mathematical function that counts the number of positive integers less than or equal to a given integer n that are relatively prime to n, meaning they do not share any common factors other than 1. It is denoted by the symbol φ(n).

2. How is the Totient Function calculated?

The Totient Function can be calculated using the formula φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where p1, p2, ..., pk are the distinct prime factors of n.

3. What is the significance of phi(n)=phi(2n) for odd n?

This equation means that for any odd integer n, the values of φ(n) and φ(2n) are equal. This is because the prime factorization of 2n will always include a factor of 2, which is not a factor of any odd number. Therefore, the Totient Function of an odd integer n will be the same as the Totient Function of its doubled value, 2n.

4. Can the equation phi(n)=phi(2n) for odd n be used to simplify calculations?

Yes, this equation can be useful in simplifying calculations involving the Totient Function. For example, if we need to find the value of φ(15), we can instead calculate φ(30) using the equation and then divide by 2, since 15 is an odd number.

5. Are there any other interesting properties of the Totient Function?

Yes, there are many other interesting properties of the Totient Function, including its close relationship with prime numbers and its use in encryption algorithms. It also has many applications in number theory and can be used to solve various mathematical problems.

Similar threads

  • Math Proof Training and Practice
2
Replies
69
Views
3K
  • Math Proof Training and Practice
3
Replies
80
Views
4K
  • Math Proof Training and Practice
3
Replies
93
Views
10K
  • Math Proof Training and Practice
3
Replies
100
Views
7K
  • Math Proof Training and Practice
3
Replies
102
Views
7K
  • Math Proof Training and Practice
2
Replies
67
Views
7K
  • Math Proof Training and Practice
3
Replies
93
Views
6K
  • Math Proof Training and Practice
4
Replies
137
Views
15K
  • Math Proof Training and Practice
2
Replies
42
Views
6K
  • Math Proof Training and Practice
2
Replies
61
Views
7K
Back
Top