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?
 A: 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$.  
A: 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$.
