# Finding the Probability that a randomly chosen integer is a square or psuedo-square

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?

• 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. Commented Oct 25, 2012 at 19:09
• Working modulo $3\cdot 5\cdot 7\cdot 11$, check all possibilities; count what fraction of them succeed. Commented Oct 25, 2012 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? Commented Oct 25, 2012 at 20:10

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$.)
• 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. Commented Oct 25, 2012 at 20:28