What is the proof of Euler's function?

  • Thread starter SrEstroncio
  • Start date
  • Tags
    Proof
In summary, this conversation is about the totient function and how it is related to prime factorization.
  • #1
SrEstroncio
62
0
Hello.
I have been reading a book with an introductory section on number theory and the part regarding Euler's function just said that [tex] \varphi (n) = n-1 [/tex] when n is prime and that [tex] \varphi (n) = n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{n}}) [/tex] when n is a composite number.
The book (What is mathematics by Richard Courant) said the proof was "completely trivial" but that they wouldn't say it and I was wondering if someone could provide a proof or guide me through one.

Thanks in advance.
 
Last edited:
Physics news on Phys.org
  • #2
Hi,
does the book say something about the value of phi when n is a power of a prime? That's a useful intermediate result.

In general, you could use a second book. (Or wikipedia.)
"Elementary number theory" by David Burton is a nice introduction.
 
  • #3
No, it does not say anything about the value of [tex] \varphi (p^{\alpha}) [/tex] but wikipedia saves the day. O was reading Wolfram's Mathworld's proof but I got lost around here:
Now let q be some other prime dividing m. The integers divisible by q are q, 2q, ..., (m/q)q. But these duplicate pq, 2pq, ..., (m/(pq))pq. So the number of terms that must be subtracted from [tex]\phi_p[/tex] to obtain [tex]\phi_{pq}[/tex] is

Here's the link.
http://mathworld.wolfram.com/TotientFunction.html
 
  • #4
I also get a little confused, because the definition of [itex]\phi_p[/itex] referred to the number of integers not divisible by p; while, when aiming at [itex]\phi_{pq}[/itex], I believe they mean now integers coprime to pq (that is, not divisible by either p, or q, or both). When p was prime it was the same thing, but as pq is composite, the distinction must be made.

For example, if you seek the number of integers (less than some limit) coprime to 6, you can discount the multiples of 2 and then discount the multiples of 3... but take in mind that you just discounted twice the multiples of 6.

However, I would have imagined a shorter way to the proof. [itex]\phi[/itex] is a multiplicative function, meaning that, for each pair of coprimes m, n, [itex]\phi(mn) = \phi(m) \phi(n)[/itex]. Now, any number has a prime factorization (can be expressed as a product of prime powers), and any two of these prime powers are coprime.

(Of course, then you should probably prove first that [itex]\phi[/itex] is multiplicative...)
 

What is Euler's function?

Euler's function, also known as the totient function, is a mathematical function that counts the positive integers up to a given integer that are relatively prime to it. It is denoted by φ(n) where n is the given integer.

What is the formula for Euler's function?

The formula for Euler's function is φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk), where n is the given integer and p1, p2, ..., pk are the distinct prime factors of n.

What is the significance of Euler's function?

Euler's function is significant in number theory and cryptography. It is used to solve problems related to prime numbers, modular arithmetic, and encryption algorithms. It is also used in the Euler's totient theorem, which states that aφ(n) ≡ 1 (mod n) for any integer a relatively prime to n.

How is Euler's function related to the prime factorization of a number?

Euler's function is related to the prime factorization of a number through its formula. It considers the distinct prime factors of a number and their powers to calculate the number of positive integers relatively prime to it.

Can Euler's function be extended to other number systems?

Yes, Euler's function can be extended to other number systems. For example, in the Gaussian integers, the Euler's function is defined as the number of Gaussian integers relatively prime to a given Gaussian integer. It can also be extended to other algebraic number systems such as the Eisenstein integers and the Hurwitz integers.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
913
  • Advanced Physics Homework Help
Replies
1
Views
1K
  • Classical Physics
Replies
17
Views
965
Replies
13
Views
1K
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
862
  • Math Proof Training and Practice
Replies
4
Views
1K
  • Advanced Physics Homework Help
Replies
4
Views
1K
Back
Top