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 think I am most of the way through this proof but I am stuck. Here was my approach: I looked at the square roots of $1$ mod $105$, and noticed that each one corresponded to one less than an integer multiple of a subset of the prime factors of $105$, i.e. we have for instance $71=24\cdot3-1$ or $29=2\cdot(3\cdot 5)-1$ and so on. I conjectured that given a subset of the prime factors of $m$, I could construct a unique square root of $1$ mod $m$, which would show that there are (at least) $2^k$ of them.

So I did that and I think that it worked. Pick some set of the prime factors of $m$, say $p_{a_1},\dots,p_{a_j}$. Claim: we can find a corresponding $n$ such that $n\prod_{i=1}^jp_{a_i}-1$ is a square root of $1$ mod $m$.

Proof: We are looking for a solution to

$$\left(n\prod_{i=1}^jp_{a_i}-1\right)^2\equiv 1 \pmod m$$ which may be rewritten as

$$\left(\prod_{i=1}^jp_{a_i}\right)^2n^2 - 2\prod_{i=1}^jp_{a_i}n\equiv 0 \pmod m$$

Now since $\prod_{i=1}^jp_{a_i}|m$ we may write this as $$\prod_{i=1}^jp_{a_i}n^2-2n \equiv 0\mod \frac{m}{\prod_{i=1}^jp_{a_i}}$$

or

$$n\left(\prod_{i=1}^jp_{a_i}n-2\right) \equiv 0 \mod {\frac{m}{\prod_{i=1}^jp_{a_i}}}$$

This has solutions when $n\equiv0\mod \frac{m}{\prod_{i=1}^jp_{a_i}}$ or when $\prod_{i=1}^jp_{a_i}n-2\equiv 0 \mod \frac{m}{\prod_{i=1}^jp_{a_i}}$. In the first case we end up with the same root for any choice of $p_{a_i}$'s so that's sort of a degenerate one. But in the second case we have $\prod_{i=1}^jp_{a_i}n\equiv 2 \mod \frac{m}{\prod_{i=1}^jp_{a_i}}$, which has a unique and nonzero solution for $n$. Plugging that $n$ back into $n\prod_{i=1}^jp_{a_i}-1$ thus gives a square root of $1$ mod $m$ which corresponds uniquely to your choice of prime factors, thus showing that there are (at least) $2^k-1$ square roots of 1. Then we add 1 in which corresponds to the empty set of prime factors and we get the full $2^k$.

My problem is ruling out the possibility of more square roots of 1, i.e. if $x^2\equiv1\mod m$ I need to show that it corresponds uniquely to something of the form $n\prod_{i=1}^jp_{a_i}-1$. This is proving to be difficult if not impossible.

I put a lot of work into going the one way and I really don't want it all to be for nothing. Can anyone see a way to go the other direction?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

Since $x^2=1 \mod (p)$ has $2$ solutions, applying then the Chinese remainder theorem.

share|improve this answer

Note $\ p_1\!\cdots p_k\mid x^2\!-1 = (x\!-\!1)(x\!+\!1) \!\iff\! p_i \mid x\!-\!1\,\ {\rm or}\,\ p\mid x\!+\!1\!\iff\! x\equiv \pm1 \pmod{ p_i}$

Therefore there are precisely $\,2^k\,$ solutions $\ x\equiv\, (\pm1,\ldots,\pm1)\ \pmod{p_1,\ldots,p_k}$

Your method amounts to bijecting each solution with the subset of primes where $\,x\equiv -1,\,$ or, equivalently, the product of primes from that subset. So the solutions are in $1$-$1$ correspondence with all subsets of $\,\{p_1,\ldots,p_k\}\,$ or, equivalently, all factors of $\,p_1\!\cdots p_k.$

share|improve this answer

To elaborate on Ma Ming's answer, note that every cyclic group $C$ of even order $2b$ has a unique element of order $2$, namely the $b$-th power of a generator, which defines an order-$2$ subgroup in $C$. Your question concerns the group $\mathbb{Z}_m^*$ which is the product of the groups $\mathbb{Z}_{p_i}^*$, each of even order. The subgroup of $\mathbb{Z}_m^*$ given by the product of the order-$2$ subgroups as above is precisely the collection of the "square roots" you are interested in. Since there are $k$ of these order-$2$ subgroups, the order of the product is $2^k$.

share|improve this answer

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.