- #1
BSMSMSTMSPHD
- 131
- 0
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?
Thanks!
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!
Last edited: