I'm trying to prove one of the properties of the “Modified Rabin Signature Scheme”:
If $\gcd(x, n) = 1$, then $x^{\frac{(p−1)(q−1)}{2}} \equiv 1 \pmod n$
This is what I’ve got so far…
Proof
Let $p$ and $q$ be primes such that $p \equiv 3 \pmod 4$ and $q \equiv 3 \pmod 4$
$$p = 4 t_1 + 3 , \, q = 4 t_2 + 3 \,\,\,\,\,\,\,\,\,\,-(I)$$
Then ($s$ = odd)
$$\frac{\phi(n)}{2} = 2 s\\$$
From the “Euler theorem” we know that
$$x^{\phi(n)} \equiv 1 \pmod n$$
Taking square root both sides
$$x^{\frac{\phi(n)}{2}} \equiv \sqrt{1} \pmod n$$
assuming
$$x^{\frac{\phi(n)}{2}} \equiv -1 \pmod n \, \text{ i.e. } \, x^{2s} \equiv -1 \pmod n\\ \implies x^{2s} -1 = nk$$
subsituting values of $p, q$ from $(I)$ we get
$$x^{\text{even}} = (\text{odd})k + 1$$
Now, I want to show that
$$x^{\text{even}} \neq (\text{odd})k + 1$$
… but I'm kind of stuck here.
Can anybody help me complete this proof of one of the properties of Modified Rabin Signature?