Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Euler Function Problem

  1. Aug 28, 2006 #1
    The Euler Function [tex] \varphi (n) [/tex] is defined as the number of natural numbers less than n that are relatively prime to n. That is, [tex] \varphi (n) = | \{ a \in \mathbb{N} | a < n [/tex] and [tex] gcd (a, n) = 1 \} | [/tex]

    I have been asked to show that if a number d divides a number n, then [tex] \varphi (d) [/tex] divides [tex] \varphi (n) [/tex]

    So far, I have that there must exist and integer k such that n = kd. Therefore, [tex] \varphi (n) = \varphi (kd) [/tex]. However, I cannot deduce from here that this equals [tex] \varphi (k) \varphi (d) [/tex], since this is only true when k and d are relatively prime, which is not guaranteed.

    So, I have tried writing k and d as products of primes and going from there, but I seem to be hitting a wall. Can I get a hint as to where I should look?

    Last edited: Aug 28, 2006
  2. jcsd
  3. Aug 28, 2006 #2


    User Avatar
    Science Advisor

    You know [tex] \varphi (n) \varphi (d) = \varphi (nd) [/tex] if n and d are relatively prime. Then note that if p and q are different prime numbers, p^k and q^k are relatively prime. So you can write them as a product of primes, split the euler functions up, and then bring them back together.
  4. Aug 28, 2006 #3
    Okay, so then I was on the right track. I just got all messed up with my p's and q's. Thanks for the response!
  5. Aug 28, 2006 #4


    User Avatar
    Science Advisor

    Actually, probably a better way to do it is to use the expansion where phi(n) = n * (1-1/p1) * ... * (1-1/pj) for the primes p1 ... pj that divide n. You have n = kd, and the factor of k either introduces new prime factors or it doesn't. If it doesn't then you've got your answer, otherwise let the new prime factors be pi...pj, and let m = pi* ... * pj. Then you have n = m * (kd/m) and you can simplify the expansion.
    Last edited: Aug 29, 2006
  6. Aug 31, 2006 #5
    Okay, here's what I came up with. I scratched the idea of looking at k and d, because I kept running into walls with that. Instead, I decided to examine n and d.

    I know this proof may be longer than necessary, but at this point, I'll be happy with just plain correct. Your comments would be very much appreciated (it's due tomorrow morning).

    We start with the fact that d divides n and write n in its prime factorization:

    [tex] n = p_1 ^{ \alpha_1} p_2 ^{ \alpha_2} \cdot \cdot \cdot p_s ^{ \alpha_s} [/tex]

    where [tex] \alpha _i \in \mathbb{N} [/tex]

    Now, introduce indexing set A, defined as: [tex] A = \{ k \in \mathbb{N} | 1 \leq k \leq s \} [/tex]

    So, more concisely, [tex] n = \prod_{i \in A} p_i ^{ \alpha_i} [/tex]

    Next, introduce indexing set B, defined as: [tex] B = \{ m \in A | p_m [/tex] divides [tex] d \} [/tex]

    Note here that B is a subset of A, since any prime that divides d must also divide n.

    Now we can write the prime factorization of d as: [tex] d = \prod_{j \in B} p_j ^{ \beta_j} [/tex]
    where [tex] 0 < \beta _j \leq \alpha_i [/tex] [tex] \forall i = j [/tex]

    Now, we are trying to show that [tex] \varphi (d) [/tex] divides [tex] \varphi (n) [/tex]. This will follow if we show that [tex] \frac {\varphi (n)}{\varphi (d)} [/tex] is an integer.

    Thus, we evaluate as follows:

    [tex] \frac {\varphi (n)}{\varphi (d)} = \frac { \varphi (\prod_{i \in A} p_i ^{ \alpha_i})}{\varphi (\prod_{j \in B} p_j ^{ \beta_j})} = \frac { \prod_{i \in A} \varphi (p_i ^{ \alpha_i})}{\prod_{j \in B} \varphi_ (p_j ^{ \beta_j})} = \frac { \prod_{i \in A} p_i ^{ \alpha_i - 1} (p_i - 1)}{\prod_{j \in B} p_j ^{ \beta_j - 1} (p_j - 1)} [/tex]

    Now, the value of this quotient depends on whether each prime divides d and n, or only divides n.

    I am conjecturing that the above quotient equals the following statement:

    [tex] \frac {\varphi (n)}{\varphi (d)} = \prod_{j \in B} p_j ^{ \alpha_j - \beta_j } \cdot \prod_{i \in A \backslash B} p_i ^{ \alpha_i - 1} (p_i - 1) [/tex]

    Furthermore, I claim that this is an integer since it is the product of integers. So it would seem that I have proven the original claim.

    Okay - how'd I do? Be gentle...
    Last edited: Aug 31, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook