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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Definition: $n$ is a psuedo-square if the legendre symbol $(\frac{n}{p}) = 0$ or $= 1$ for $p = 3, 5, 7, 11$.

I want to find the probability of $n$ being a square or psuedo-square. I know that any square will satisfy the property of being a psuedo-square so it remains to find the probability of being a psuedo-square.

By Euler's Criterion:

$n^{\frac{p-1}{2}} \equiv (\frac{n}{p}) \mod p \iff$ $n$ is a quadratic residue modulo $p$.

So consider the cases for $n$ to be a psuedo-sqaure. That is $(\frac{n}{p}) = 0$ or $1$ when $p = 3,5,7,11$ and we get the following:

$n \equiv 1 \mod 3$ or $3|n$

$n^2 \equiv 1 \mod 5$ or $5|n$

$n^3 \equiv 1 \mod 7$ or $7|n$

$n^5 \equiv 1 \mod 11$ or $11|n$

Is this the correct line of thinking? How can I proceed to solve these congruences and then to find the probability?

share|cite|improve this question
It is not probability, it is natural density. The line of thinking is good. Solving the congruences can be done in a theory-free way. – André Nicolas Oct 25 '12 at 19:09
Working modulo $3\cdot 5\cdot 7\cdot 11$, check all possibilities; count what fraction of them succeed. – mjqxxxx Oct 25 '12 at 20:07
I have $\frac{2}{3} \mod 3$ and $\frac{3}{5} \mod 5$ and $\frac{4}{7} \mod 7$ and $\frac{6}{11} \mod 11$ What does this mean? – CodeKingPlusPlus Oct 25 '12 at 20:10
up vote 1 down vote accepted

The most straightforward way of solving the congruences is simply via trial and error. For instance, consider $n^3\equiv 1\bmod 7$ or $7|n$ (which can also be written as $n^3\equiv 0\bmod 7$). Cubing the values $0\ldots 6$ we find $0^3=0$, $1^3=1$, $2^3=1$, $3^3=6$, $4^3=1$, $5^3=6$, $6^3=6$; thus, a number satisfies the '$\bmod 7$' test if it is $0$, $1$, $2$ or $4$, and it has probability (as André notes in a comment, the more accurate term here would be natural density) $\frac{4}{7}$ of passing this test. You can do a similar analysis for the other cases (and you should notice a pattern in the answers - it's worth asking yourself where it comes from!).

Once you have the individual results, combining them is a relatively basic exercise; if you can convince yourself that the probability of $n$ being e.g. $4\bmod 5$ is completely independent of $n$ being $2\bmod 7$, then you should be able to see why you can just multiply out the individual probabilities. (More formally, you can use the Chinese Remainder theorem to see why e.g. each pair $a = n\bmod 5$, $b = n\bmod 7$ corresponds to a unique number $c = n\bmod 35$.)

share|cite|improve this answer
Could you show me how all of the densities are independent? My brain tells me they are unrelated, but how do I put this in terms of independence? – CodeKingPlusPlus Oct 25 '12 at 19:47
The CRT is the trick: for instance, since as I noted every (mod 5, mod 7) pair yields a unique number mod 35, your 3 pseudosquares mod 5 and 4 pseudosquares mod 7 yield 12=3*4 numbers mod 35 that fit both the mod 5 and mod 7 criteria, and thus an overall $\frac{12}{35}=\frac{3}{5}\cdot\frac{4}{7}$ proportion of numbers satisfying both conditions. – Steven Stadnicki Oct 25 '12 at 20:28

Your Answer


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.