Let $n$ be an integer different from $2,4,p^{\alpha}$ and $2p^{\alpha}$; ($p$ is odd prime).

Using just elementary number theory (not group isomorphism), prove that $$a^{\varphi(n)/2}=1 \mod n$$ (I have proved it using group isomorphism and order of elements, but i want an elementary proof).

  • 1
    $\begingroup$ $n = 12$, I suppose, $\varphi(12) = 4$, but $2^2 \neq 1 \mod 12$ $\endgroup$
    – dEmigOd
    Jul 15, 2018 at 11:47
  • $\begingroup$ math.stackexchange.com/questions/114841/… $\endgroup$ Jul 15, 2018 at 11:53
  • 1
    $\begingroup$ To me it looks like the point of the hypotheses is that n can be written as xy where gcd(x,y) = 1 and where phi(x) and phi(y) are both even. This implies phi(n)/2 is divisible by phi(x) and is divisible by phi(y). Then use the Chinese Remainder Theorem and Euler's Theorem. (I don't think the linear-algebra tag is appropriate.) $\endgroup$
    – CJD
    Jul 15, 2018 at 11:54
  • $\begingroup$ I mean by $a$ is an element of the multiplicatif group $\left(\mathbb{Z}/n\mathbb{Z}\right)^*$; so in the example $a=2$ modulo $12$ will not work. @dEmigOd $\endgroup$
    – C.S.
    Jul 15, 2018 at 12:16

1 Answer 1


Note that the integer $n\geq 2$ can only be of two types: either $n=2^l$, with $l\geq 3$, or $n=mp^k$, with $p$ odd prime number, $k\geq 1$, $m\geq 3$ and $p\nmid m$.

Case $n=2^l$, with $l\geq 3$.

We prove that for each odd number $a$ we have $$ a^{\varphi(2^{l})/2)} \equiv 1\pmod{2^l}. $$ We argue by induction on $l\geq 3$. If $l=3$ we write $a=2h+1$ for a certain integer $h$, and thus $$ (2h+1)^2=4h(h+1)+1=8\cdot \frac{h(h+1)}{2}+1\equiv 1\pmod{8}. $$ For the inductive step we suppose $a^{2^{l-2}}\equiv 1\pmod{2^l}$ for a certain $l\geq 3$. We thus have $$ a^{2^{l-1}}=\left(a^{2^{l-2}}\right)^2 \overset{(1)}{=} (1+h\cdot 2^l)^2=1+h\cdot2^{l+1}+h^22^{2l}\equiv 1\pmod{2^{l+1}}, $$ where in (1) we used the inductive hypothesis.

Case $n=mp^k$, with $p$ odd prime number, $k\geq 1$, $m\geq 3$ and $p\nmid m$.

By multiplicativity of $\varphi$ we have $\varphi(n)=\varphi(m)\varphi(p^k)$. Moreover, $\varphi(m)$ is even since $m\geq 3$ and $\varphi(p^k)=p^{k-1}(p-1)$ is even since $p$ is odd. For each integer $a$ with $(a,n)=1$ we thus have $$ a^{\varphi(n)/2} = (a^{\varphi(m)})^{\varphi(p^k)/2} \equiv 1\pmod{m} $$ and $$ a^{\varphi(n)/2} =(a^{\varphi(p^k)})^{\varphi(m)/2} \equiv 1\pmod{p^k}. $$ By Chinese Remainder Theorem follows $a^{\varphi(n)/2}\equiv 1\pmod{n}$.


Not the answer you're looking for? Browse other questions tagged .