Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.


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

share|cite|improve this answer
So my mistake was using Fermat's little theorem (applied to the two primes) rather than Euler's theorem (applied to two co-prime factors containing the two primes). – jaakhaamer Sep 10 '12 at 1:34

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.