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?


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

  • 2
    $\begingroup$ 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). $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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