I'm trying work on problem 11 of Chapter 3 in Ireland and Rosen's Number Theory.

Suppose $\{a_1,\dots,a_{\phi(n)}\}$ is a reduced residue system modulo $n$. Let $N$ be the number of solutions to $x^2\equiv 1\pmod{n}$, then $$ a_1\cdots a_{\phi(n)}\equiv (-1)^{N/2}\pmod{n}. $$

How can this be shown? I know that if $n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$, then $N=\prod N(p_i^{\alpha_i})$ where $N(p_i^{\alpha_i})$ denotes the number of solutions to $x^2\equiv 1\pmod{p_i^{\alpha_i}}$.

Also, if $x_0$ is a solution, then it is also a solution to $x^2\equiv 1\pmod{p_i}$ for any prime in the factorization of $n$. This implies that $x_0\equiv \pm 1\pmod{p_i}$, so that $x_0$ is coprime to all prime factors of $n$, and thus coprime to $n$.

But I'm not seeing a connection between the left and right hand side products of the congruence in question. Thanks.

  • $\begingroup$ The half-power is misleading if you did the problems up to this point and figured that half-powers were a result of computations like $x=m/x$ so $x^2=m$. $\endgroup$ – peoplepower Dec 28 '12 at 9:57

Think about how you prove Wilson's theorem.

$(p-1)!$ can really be viewed a product over all elements of the group $(\mathbb{Z}/p\mathbb{Z})^{\times}$. Now each element in this product has an inverse mod $p$ and so when actually calculating this product mod $p$ all terms will cancel...except those that are self inverse.

What are the self inverse elements? Well those are the ones such that $x^2 \equiv 1 \bmod p$, (i.e. $1,p-1$). Thus $(p-1)! \equiv (1)(p-1) \equiv -1 \bmod p$.

The exact same proof will work for this more general theorem except the group is now $(\mathbb{Z}/n\mathbb{Z})^{\times}$ and you have more self inverse elements (denoted $b_1, b_2, ..., b_{N}$ where $N$ is the number of solutions to $x^2 \equiv 1 \bmod n$).

Thus as earlier: $a_1 a_2...a_{\phi(n)} \equiv b_1b_2 ... b_{N} \bmod n$.

Now it is not difficult to see that $N$ must be even. Also if $c$ is self inverse then $n-c$ is too (compare this with the mod $p$ case). Then the product $c(n-c) \equiv -c^2 \equiv -1 \bmod n$.

So pairing the $b$'s in this way we see that:

$b_1 b_2... b_N \equiv (-1)^{\frac{N}{2}} \bmod n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.