Show that $c^{\varphi(m)/2} \equiv 1 \pmod{m}$ if $m$ has two odd prime divisors The following problem is one of the exercises in Topics in the Theory of Numbers (Erdős et al.)

Show that if the positive integer $m$ has at least two distinct odd prime divisors, and $c$ is relatively prime to $m$, then $c^{\varphi(m)/2} \equiv 1 \pmod{m}$.

I am attempting to solve this problem using any of the tools developed before this point in the book.
My current attempt involves using Euler's product formula to write
$$\varphi(m) = \prod_{p \mid m} p^{k - 1} (p - 1).$$
Applying Fermat's little theorem gives me
$$c^{p - 1} \equiv 1 \pmod{p}$$
for every $p \mid m$.
I then reason that since at least two of the prime factors are odd, we have that $(p - 1) \mid \phi(m) / 2$, so that
$$c^{\phi(m) / 2} \equiv 1 \pmod{p}$$
for every $p \mid m$. This is where I get stuck. I am unsure how to lift the result to modulo $m$. As I understand, Hensel's lemma may be useful in this regard, but it has not yet been discussed before this point in the book. Is there a way to salvage my attempted proof without Hensel's lemma? Otherwise, does someone have a different idea that uses similar elementary theorems?
 A: You are on the right track...
But you need to do this not $\mod p$ but modulo $p^\alpha$, where $\alpha$ is the largest power of $p$ dividing $n$.
Then, if 
$$c^{\phi(m) / 2} \equiv 1 \pmod{p_k^{\alpha_k}}$$
for all $k$, what does Chinese Remainder Theorem sais?
A simpler proof: Basically this is your idea of proof simplified.
Write $m=ab$ with $\gcd(a,b)=1$ and both $a,b$ having an odd prime divisor. This is possible by the condition in the problem.
Then $\phi(m)=\phi(a) \phi(b)$ and both $\phi(a), \phi(b)$ are even.
Thus
$$\phi(a) \frac{\phi(b)}{2} = \frac{\phi(m)}{2}\,.$$
and since $\phi(b)$ is even, we get $\phi(a)|\frac{\phi(m)}{2}$. Similarly $\phi(b)|\frac{\phi(m)}{2}$.
By Euler theorem, it follows that
$$c^{\phi(m) / 2} \equiv 1 \pmod{a} \,;\, c^{\phi(m) / 2} \equiv 1 \pmod{b} \,.$$
Again, Chinese Remainder Theorem finishes the proof. Alternately, it follows that $a,b | c^{\phi(m) / 2} - 1$, and since $\gcd(a,b)=1$ we get 
$$m=ab | c^{\phi(m) / 2} - 1 \,.$$
A: We can use Carmichael Function here,
Let $(a,b)=gcd(a,b), [a,b]=lcm(a,b)$
If $n=\prod{ p_i^{q_i}}$  where $p_i$s are distinct primes and integer $q_i$s$>0$.
$\lambda(n)=[\lambda({ p_i^{q_i}})]_i=[\phi({ p_i^{q_i}})]_i$
Now $[\phi( p_i^{q_i})]_i≤\frac{\prod \phi( p_i^{q_i})_i}{(\phi( p_i^{q_i}))_i}$
$=\frac{\phi(n)}{(\phi( p_i^{q_i}))_i}$
$2\mid (\phi( p_i^{q_i}))_i$ if at least two of $p_i$s are odd or at least one of $p_i$s is odd and one $p_i^{q_i}=2^r$  where integer $r>1$.
Then $\lambda(n)\mid \frac{\phi(n)}{2}$, that is exactly why numbers in the above form do not have primitive root.
