Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  peoplepower Dec 28 '12 at 9:57

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
Thanks fretty. ${}$ –  Noomi Holloway Dec 28 '12 at 10:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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