# How many squares are there modulo a Mersenne prime?

Mersenne primes are primes of the form $M_n = 2^n - 1$. I'm wondering how many distinct natural numbers result from squaring the naturals modulo $M_n$.

As an example, $M_3 = 7$. If we take the naturals less than seven, we get:

$$1^2 \equiv 1 \bmod 7$$ $$2^2 \equiv 4 \bmod 7$$ $$3^2 \equiv 2 \bmod 7$$ $$4^2 \equiv 2 \bmod 7$$ $$5^2 \equiv 4 \bmod 7$$ $$6^2 \equiv 1 \bmod 7$$

Thus, there are $3$ distinct results of squaring; namely $1$, $2$, and $4$. So I'm wondering, for a given Mersenne prime $M_n$, how many different squares can we get?

## 2 Answers

For any odd prime $p$, there are $\frac{p-1}{2}+1=\frac{p+1}{2}$ squares modulo $p$.

To show this, note first that $0$ is a square modulo $p$. It is, modulo $p$, $0^2$, or, if you prefer, it is congruent to $p^2$. (But it is not called a *quadratic residue of $p$.)

Now consider the squares of numbers in the interval $\left[1,\frac{p-1}{2}\right]$. These are all distinct modulo $p$. And since the numbers in the interval $\frac{p+1}{2}$ to $p-1$ are the negatives (modulo $p$) of numbers in the interval $\left[1,\frac{p-1}{2}\right]$, squaring them produces nothing new. You will observe this from the example you calculated. The squares of $1$, $2$, and $3$ were distinct modulo $7$, and after that you got nothing new.

To show that squares of numbers in the interval $\left[1,\frac{p-1}{2}\right]$ are all distinct modulo $p$, let $x$ and $y$ be numbers in the interval, with $x\gt y$. Suppose $x^2\equiv y^2\pmod{p}$. Then $(x-y)(x+y)$ is divisible by $p$. Thus one of them is. That's impossible, since each of $x-y$ and $x+y$ lies between $1$ and $p-1$.

For any (odd) prime $p$, there exists some primitive root $m\pmod p$ whose order is $\phi(p)=p-1$. The quadratic residues (squares) modulo $p$ are precisely the even powers of $m$, of which there are $\frac{p-1}{2}$, unless you'd like to include $0$ (which generally isn't considered a quadratic residue), in which case our total becomes $\frac{p+1}{2}$

So, for a Mersenne prime $M_n=2^n-1$, we should have $2^{n-1}-1$ squares, or $2^{n-1}$ including $0$.