Online Course Discussion Forum

MCIII 4.5 and 4.6 and 4.7

 
 
Picture of Tina Jin
MCIII 4.5 and 4.6 and 4.7
by Tina Jin - Saturday, 30 December 2023, 10:46 PM
 

Hello!

I have no idea how to do 4.5. I tried plugging in functions but it just got very tedious.

For 4.6 I realized that 3 cannot divide (pi-1) for any i. But I'm not sure how to find the prime numbers, I know they have to be congruent to 2 mod 3, but I listed 2, 5, 11, 17, 23, 29, 41, 47, 53, 39, 71, and there seems to be infinitely many more. How should I proceed?

For 4.7 I tried analyzing both sides as the number of numbers that are relatively prime to something else, and I seem to be getting a contradiction and I don't know how to solve this problem.

Thank you!

Tina Jin

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