TAOCP 3.2.1.2 Exercise 10

From (9), $\lambda(m)=\varphi(m)$ holds for odd prime powers $p^e$, since $\lambda(p^e)=p^{e-1}(p-1)=\varphi(p^e), \qquad p>2.$ For powers of $2$, $\lambda(2)=1=\varphi(2),\qquad \lambda(4)=2=\varphi(...

taocpmathematicsalgorithmsvolume-2

Section 3.2.1.2: Choice of Multiplier

Exercise 10. [**] [M21] For what values of $m$ is $\lambda(m) = \varphi(m)$?

Verified: yes
Solve time: 1m34s

From (9), $\lambda(m)=\varphi(m)$ holds for odd prime powers $p^e$, since

$\lambda(p^e)=p^{e-1}(p-1)=\varphi(p^e), \qquad p>2.$

For powers of $2$,

$\lambda(2)=1=\varphi(2),\qquad \lambda(4)=2=\varphi(4),$

but for $e\ge3$,

$\lambda(2^e)=2^{e-2}<2^{e-1}=\varphi(2^e).$

If

$m=p_1^{e_1}\cdots p_t^{e_t},$

then

$$$$

while

$$$$

The least common multiple of positive integers equals their product if and only if they are pairwise relatively prime. Hence $\lambda(m)=\varphi(m)$ exactly when the numbers $\varphi(p_j^{e_j})$ are pairwise relatively prime and no factor $2^e$ with $e\ge3$ occurs.

Since every $\varphi(p_j^{e_j})=p_j^{e_j-1}(p_j-1)$ for odd $p_j$ is even, there can be at most one odd prime-power factor. Therefore the only possibilities are

$$$$

where $p$ is an odd prime. In all these cases,

$\lambda(m)=\varphi(m).$

Therefore

$\boxed{\lambda(m)=\varphi(m)\ \text{if and only if}\ m=2,\ 4,\ p^e,\ \text{or}\ 2p^e,\ \text{with }p\text{ an odd prime}.}$

∎