Why is $x^{\frac{n-1}{2}}\not \equiv 1 \mod n$

Question

If $n=p_1p_2\cdots p_r$ and $g_1$ is the generator of $U(Z_{p_1})$. Then let $x$ be an integer such that $x\equiv 1 \mod p_2p_3\cdots p_r$ and $x\equiv g_1\mod p_1$ I would like to prove that $x^{\frac{n-1}{2}}\not \equiv 1\mod n$ but I do not know how. Any hint would be appreciated.

Answer 1

What you're asking to prove is not always true. A fairly simple counter-example is $r = 2$, $p_1 = 3$ with a generator (i.e., primitive root) of $g_1 = 2$, and $p_2 = 7$. In this case, you have $n = 3(7) = 21$, plus

$$x \equiv 1 \pmod{7} \tag{1}\label{eq1A}$$

$$x \equiv 2 \pmod{3} \tag{2}\label{eq2A}$$

The solution is $x \equiv 8 \pmod{21}$. Note you have

$$x^2 \equiv 64 \equiv 1 \pmod{21} \tag{3}\label{eq3A}$$

so you then get

$$x^{\frac{n-1}{2}} \equiv x^{10} \equiv \left(x^2\right)^5 \equiv 1 \pmod{21} \tag{4}\label{eq4A}$$

Are there perhaps some additional conditions which weren't mentioned?

Answer 2

What you are trying to prove is equivalent to $x^{(n-1)/2}=g_1^{(n-1)/2}\neq 1\mod p_1$. This is equivalent to $(n-1)/2$ not being divisible by $p_1-1$. But this is not necessarily true ($p_1=3, n=21$).