Another Euler Phi function

[bigp0ppa1046]

a) If m≥3, explain why Φ(m) is always even.
b) Φ(m) is “usually” divisible by 4. Describe all the m’s that for which Φ(m) is not divisible by 4.

 

[soroban]

Hello, bigp0ppa1046!

Here's part (a) . . . I'm still working on part (b).

a) If \(\displaystyle m\,\geq\,3\), explain why \(\displaystyle \phi(m)\) is always even.

b) \(\displaystyle \phi(m)\) is “usually” divisible by 4.
Describe all \(\displaystyle m\) that for which \(\displaystyle \phi(m)\) is not divisible by 4.

Since \(\displaystyle m \:=\:2^a\cdot3^b\cdot5^c\cdot7^d\cdots\) and \(\displaystyle m\,\geq\,3\), there are two cases:

(1) \(\displaystyle \,a\,\geq\,2\,\) and \(\displaystyle \,b,c,d,...\,=\,\text{any}\)

Then: \(\displaystyle \,\phi(m) \:=\:\underbrace{2^{a-1}}(2-1)\cdot3^{b-1}(3-1)\cdot5^{c-1}(5-1)\cdot7^{d-1}(7-1)\cdots\)
. . . . . . . . . . . even

(2) \(\displaystyle a\,=\,0,1\,\) and at least one of \(\displaystyle b,c,d,...\) is at least \(\displaystyle 1.\)

then: \(\displaystyle \:\phi(m) \:=\:2^{a-1}(2-1)\cdot3^{b-1}\underbrace{(3-1)}\cdot5^{c-1}\underbrace{(5-1)}\cdot7^{d-1}\underbrace{(7-1)} \cdots\)
. . . . . . . . . . . . . . . . . . . . at least one of these is even