Order of an element modulo $n$ divides $\varphi(n)/2$. 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).
 A: 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}$.
