Primitive roots are magic

Number Theory Level 5

$\displaystyle \left( \prod _{\text{ord}(n)<p-1}^{}{ n } \right) \pmod{1601}$

Consider the prime number $1601$ . Let $\text{ord}(x)$ denote the least $j>0$ such that $x^j\equiv 1 \pmod{1601}$ . Evaluate the product above over the set of nonzero residues modulo $1601$ .

The answer is 1600.

2 solutions

Otto Bretscher
Nov 3, 2015

Note that $ord(n)=ord(n^{-1})$ , where $n^{-1}$ is taken modulo 1601. Thus all the products $n*n^{-1}$ cancel out, except for $n=n^{-1}=-1$ , so that the product is $-1\equiv \boxed{1600} \pmod{1601}$

Moderator note:

Pairing up terms is the nice way to showing the result. It works for wilson's theorem with a clear pairing.

Watch out that in the above solution, the other product that doesn't "cancel out" is when $n = n^{-1} = 1$ , because we have a repeated term. However, it contributes a term of 1, which doesn't affect the product.

Dylan Pentland
Nov 3, 2015

If we disregard the condition $ord(n)<p-1$ then we have by Wilson's theorem

$\prod_ {n=1}^{p-1}{n} \equiv -1 \pmod{p}$

and that by introducing the condition in the problem we remove all primitive roots from the product. Thus, if the value of the desired product is $a$ and $g_1, g_2 ... g_{\phi(p-1)}$ are the primitive roots then

$a \left( \prod_ {n=1}^{\phi(p-1)}{g_n} \right) = -1$

Now, we just need $\prod_ {n=1}^{\phi(p-1)}{g_n}$ . It's pretty well known that this product is just one mod $p$ , but I left a proof as a comment. Using that it's one, we get $a\times 1 = -1$ so $a=-1$ . So the answer is 1600!

First, re-write the product of the primitive roots.

$\Large \prod_ {n=1}^{\phi(p-1)}{g_n} = \prod_ {gcd(i,p-1)=1}^{}{{g_1}^{i}} = {g_1}^{\sum_ {gcd(i,p-1)=1}^{}{i}}$

Fortunately, we have the property that if $gcd(i,p-1)=1$ then $gcd(p-1-i,p-1)=1$ . Hence, we get $\phi(p-1)$ pairs summing to $p-1$ so the product is just

$\displaystyle{g_1}^{\frac{\left(\phi(p-1)\right) (p-1)}{2}} = 1$

since $\phi(p-1)$ is even and therefore we are raising to a power 0 mod p-1, giving 1.

Dylan Pentland - 5 years, 7 months ago

Can you clarify the Latex in your first equation? Thanks!

Calvin Lin Staff - 5 years, 7 months ago

I made it bigger, hopefully it's readable now.