# Order of an element modulo $n$ divides $\varphi(n)/2$. [duplicate]

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).

• $n = 12$, I suppose, $\varphi(12) = 4$, but $2^2 \neq 1 \mod 12$ Jul 15, 2018 at 11:47
• math.stackexchange.com/questions/114841/… Jul 15, 2018 at 11:53
• 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.)
– CJD
Jul 15, 2018 at 11:54
• 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
– C.S.
Jul 15, 2018 at 12:16

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}$$.