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](adsbygoogle = window.adsbygoogle || []).push({});

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?

Thanks!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Euler Function Problem

**Physics Forums | Science Articles, Homework Help, Discussion**