Online Course Discussion Forum

MCIII 4.5 and 4.6 and 4.7

 
 
Picture of Dr. Kevin Wang
Re: MCIII 4.5 and 4.6 and 4.7
by Dr. Kevin Wang - Monday, 8 January 2024, 12:44 AM
 

4.5: It does help to evaluate for $n=1, 2, 3, 4$ and see if there is a pattern.  To make it less tedious, you can evaluate $\mu(n)$ first, then the Mobius transform of each $n$ is the sum of certain $\mu(k)$ values.  After trying small values, you may want to try $p^k$, powers of primes.

4.6: We are not limited to prime numbers.  Your conclusion is correct that for any prime factor $p_i$ of $n$, $3$ cannot divide $p_i - 1$.  So you can say the number $n$ does not have prime factors of the form $3k+1$ for any $k$.  However, this is not all the restrictions.  If you examine the formula for $\phi(n)$ carefully, you need that $n$ cannot have two factors of $3$.  Thus you also add the requirement that $9\nmid n$.

4.7: Use the formula $$\phi(n) = n\prod_{i=1}^k \left( 1 - \frac{1}{p_i}\right),$$ where $p_i$ are the prime factors of $n$.