4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.