Monday, December 1, 2014

Product of all numbers

A prime $p$ is called "good" if there is an $m$ such that $p$ divides $m^2 - 2$. For example, 7 and 17 are good primes. Suppose $p$ is a good prime. Consider all numbers in the form of $a\sqrt{2} + b$ where $a,b \in \{0, \dots, p-1\}$ and $(a,b) \neq (0,0)$. The product of all those numbers can be written as $s\sqrt{2} + t$ where $s$ and $t$ are integers. Find their remainders modulo $p$. What if $p$ is not a good prime?

Solution

If $p$ is a good prime then $s \equiv t \equiv 0 \mod p$. If $p$ is not a good prime, then $s \equiv 0, t \equiv -1 \mod p$

Proof:

Define the "~" (equivalency) as follows: two numbers $s \sqrt{2} + t$ and $u\sqrt{2} + v$ are equivalent if $s \equiv u$ and $t \equiv v \mod p$. Then we readily see that the following properties are easy to show:

$X \sim X$ (reflexivity).

$X \sim Y \iff Y \sim X$ (symmetry).

If $X \sim Y$ and $Y \sim Z$ then $X \sim Z$ (transitivity).

Given these three then equivalency divides all numbers in te form $s\sqrt{2}+t$ into equivalency classes. Furthermore we see that:

If $X \sim Y$ and $W \sim Z$ then $X+W \sim Y+Z$ and $XW \sim YZ$. It follows directly from the properties of modular arithmetics.

Now, if $p$ is a good prime, then note that $(\sqrt{2} + m)(\sqrt{2} + p-m) = (2-m^2 + pm) + p\sqrt{2} \sim 0$. Thus the product of all numbers in question is equivalent to zero.

If $p$ is not a good prime, it's a lot more complicated.

First we claim the following: given $X \nsim 0$, then there exists $Y$ such that $XY \sim 1$. We call this $Y$ the inverse of $X$.

Proof: Given a number $a\sqrt{2} + b$, first we define the number $r$ as follows: $r \in (0, \dots, p-1)$ such that $r(b^2-2a^2) \equiv 1 \mod p$.

This $r$ must exist, because $b^2 - 2a^2 \not\equiv 0 \mod p$, for otherwise we have $(ba^{-1})^2 \equiv 2 \mod p$, a contradiction.

Then consider the number $ar\sqrt{2}-br$. The product of this and $a\sqrt{2} + b$ is: $$(ar\sqrt{2}-br)(a\sqrt{2} + b) = (2a^2-b^2)r \sim 1$$

Then we prove the second claim: If $XY \sim 0$ then either $X \sim 0$ or $Y \sim 0$.

Proof:

Let $X = a\sqrt{2}+b, Y = c\sqrt{2}+d$ then $XY = (bc+ad)\sqrt{2}+(2ac+bd) \sim 0$ so we have: $$bc+ad \equiv 0 \mod p$$ $$2ac+bd \equiv 0 \mod p$$ Assuming that both $X,Y$ are not equivalent to zero, either $c \neq 0$ or $d \neq 0$ because otherwise $Y \sim 0$. If $d \neq 0$ then: $$abc \equiv -a^2d \mod p$$ $$2abc \equiv - b^2d \mod p$$ $$\Rightarrow b^2d \equiv 2a^2d \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ A contradiction. If $c \neq 0$ then we similarly show: $$abd \equiv - b^2c \mod p$$ $$abd \equiv -2a^2c \mod p$$ $$(ba^{-1})^2 \equiv 2 \mod p$$ Also a contradiction. (The assumption that $X \nsim 0$ is needed to take inverse of $a$)

So based on the second claim, we now assert that each number in the problem statement has an inverse, and the inverse is unique. For if $XY \sim XZ \sim 1$ then $X(Y-Z) \sim 0$ so $Y \sim Z$. This means that a lot of pairs among those numbers would multiply 1. The only numbers left are those who are inverses with itself. To find such numbers, note the following:

$$X^2 = 2ab\sqrt{2} + (2a^2+b^2) \sim 1$$ $$\iff ab \equiv 0, 2a^2+b^2 \equiv 1 \mod p$$ If $a \equiv 0$ then $b^2 \equiv 1$, so $p$ divides $b^2-1 = (b+1)(b-1)$. The only possible $b$ are $1, p-1$, and these numbers are in the problem statement.

If $b \equiv 0$ then $2a^2 \equiv 1$ which means $2 \equiv (a^{-1})^2 \mod p$, a contradiction.

So the only numbers who don't "cancel out" with other numbers are 1 and -1, and they're included in the final product. Thus the product of all those numbers is $\sim -1$.