3
$\begingroup$

Let $p$ be a prime number. How will numbers get distributed in $\mathbb{Z_{p}}$ upon doing $x^2 \pmod p$ where $x \in [0,p]$ is an integer?

My approach: Let $p = 97$. Then, $x^2 \equiv (97-x)^2 \pmod{97}$ (where $x$ is an integer less than $97$) because:

$$(97-x)^2 \equiv (97^2+x^2-2\cdot97\cdot x) \equiv x^2 \pmod{97}$$

So, I am sure that half, or less than half (let it be $N$), of the numbers of $\mathbb{Z_{97}}$ will get distributed. Also out of these two possibilities I have this intuition that this number $N$ would be half $(\frac{97-1}{2}+1)$, but I need to support my intuition with a proper proof.

Example: The values of $x^2 \pmod{97}$ are (for numbers 1 through 96): $$1,4,9,16,25,36,49,64,81,3,..................,3,81,64,49,36,25,16,9,4,1$$

Please help me to prove or disprove my intuition for any $p$.

$\endgroup$
  • 1
    $\begingroup$ Good intuition! Note that $x^2$ and $y^2$ are identical mod $p$ iff $p$ divides $x^2-y^2 = (x-y)(x+y)$. This is in turn equivalent to $p$ dividing at least one of $x-y$ or $x+y$, in other words, $x\equiv \pm y \pmod p$. That means all the values $0^2,1^2,\ldots,48^2$ are distinct. $\endgroup$ – Erick Wong Apr 23 '17 at 1:43
  • $\begingroup$ If you know a little group theory, this post may be useful. $\endgroup$ – André 3000 Apr 23 '17 at 1:53
1
$\begingroup$

Let $p$ be an odd prime, with $p = 2n+1$. Then we want to show that all of $1^2, 2^2, \ldots, n^2$ are distinct modulo $p$.

So it's enough to show that if $1 \le a < b \le n$, then $b^2 - a^2$ is not divisible by $p$. Now $b^2 - a^2 = (b-a)(b+a)$. But $b-a$ and $b+a$ are both positive and less than $p$, so they can't be divisible by $p$. So $b^2 - a^2$ isn't divisible by $p$. (Note that if $p$ is not prime, this breaks down! For example if $p = 15$ then we have $7^2 - 2^2 = (7-2)(7+2) = 5 \times 9 = 45$.)

So no two of $1^2, 2^2 \ldots, n^2$ are congruent mod $p$, and therefore they are $n$ different numbers, as you wanted.

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