Show that $c^{\varphi(m)/2} \equiv 1 \pmod{m}$ if $m$ has two odd prime divisors

Question

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?

Answer 1

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

Answer 2

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.