Suppose n = pq where p and q are distinct odd prime numbers. Show that, out of the φ(n) different integers c satisfying 1 < c < n and gcd(c,n) = 1, at most $\frac{φ(n)}{4}$ of them have the property that the multiplicative order of c mod n is odd.
Attempt
Let the multiplicative order of c be x: $$ord_n(c) = x$$ It means $$c^x \equiv 1 \mod n$$ Since gcd(c,n)=1, then $x|φ(n)$ $$ φ(n)\\ =φ(pq)\\ =φ(p)φ(q)\\ =(p-1)(q-1) $$ So $x|(p-1)$ or $x|(q-1)$, but not both, since we are looking for odd x, but p-1 and q-1 are even.
There are at least $\phi(p-1)$ numbers can be a divisor of p-1.
Out of these numbers, some $\frac{p-1}{2}$ will be prime. So: $$\phi(p-1)>1+\phi(\frac{p-1}{2})=1+(\frac{p-1}{2}-1)=\frac{p-1}{2}$$ $$\phi(q-1)>\frac{q-1}{2}$$
Here's an outline . . .
Let $G=\bigl\{c\in\{1,...,n-1\}\mid\gcd(c,n)=1\bigr\}$ represent the group of units, mod $n$.
Let $H=\{c\in G\mid\text{ord}(c)\;\text{is odd}\}$.
Show that $H$ is closed under multiplication, hence $H$ is a subgroup of $G$.
The set $\bigl\{\{c,c^{-1}\}\mid c\in H\bigr\}$ is a partition of $H$ (why?), and for all $c\in H$ with $c\ne 1$, the set $\{c,c^{-1}\}$ has cardinality $2$ (why?).
It follows that $H$ has odd order.
But the order of $G$ is $\phi(n)=(p-1)(q-1)$ which is a multiple of $4$.
Then $|G/H|=|G|/|H|\ge 4$, hence $|H|\le\phi(n)/4$.