Proving the Divisibility of the Euler Function: A Number Theory Problem

[BSMSMSTMSPHD]

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

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

So far, I have that there must exist and integer k such that n = kd. Therefore, \varphi (n) = \varphi (kd). However, I cannot deduce from here that this equals \varphi (k) \varphi (d), 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?

Thanks!

 

[0rthodontist]

You know \varphi (n) \varphi (d) = \varphi (nd) 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.

 

[BSMSMSTMSPHD]

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!

 

[0rthodontist]

Actually, probably a better way to do it is to use the expansion where phi(n) = n * (1-1/p₁) * ... * (1-1/p_j) for the primes p₁ ... p_j 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 p_i...p_j, and let m = p_i* ... * p_j. Then you have n = m * (kd/m) and you can simplify the expansion.

 

[BSMSMSTMSPHD]

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:

n = p_1 ^{ \alpha_1} p_2 ^{ \alpha_2} \cdot \cdot \cdot p_s ^{ \alpha_s}

where \alpha _i \in \mathbb{N}

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

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

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

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: d = \prod_{j \in B} p_j ^{ \beta_j}
where 0 < \beta _j \leq \alpha_i \forall i = j

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

Thus, we evaluate as follows:

\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)}

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:

\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)

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