order of x relatively prime to N

Question

Will it be true that for any composite number $N$ with $$N=p_1^{\alpha_1}...p_m^{\alpha_m}$$ ($p_i$: odd prime, $\alpha_i\geq1$, $m\geq2$) and any $x$ with $$\gcd(x,N)=1$$ satisfies $$x^{\frac{\phi(N)}{2^{m-1}}}\equiv1\mod N$$? ($\phi(N)$ is Euler's phi function.) It can be thought as an extension for Euler's theorem.. and for some simple cases N=15, 33, 35, 45, and 105 it was true. Will it be true for all N and x?

Answer 1

It is true. It is enough to show that for any $i$, we have $$x^{\frac{\varphi(N)}{2^{m-1}}}\equiv 1\pmod{p_i^{\alpha_i}}.\tag{1}$$ For notational simplicity, let $i=1$. Note that $$\varphi(N)=\varphi(p_1^{\alpha_1})\prod_2^m \varphi(p_j^{\alpha_j}).$$ The $\varphi(p_j^{\alpha_j})$ are all even, so $$\varphi(N)=\varphi(p_1^{\alpha_1})2^{m-1}K$$ for some integer $K$.

Thus $\frac{\varphi(N)}{2^{m-1}}$ is a multiple of $\varphi(p_1^{\alpha_1})$, and Congruence 1 follows by Euler's Theorem.

Remark: For a generalization, please search under Carmichael function.