# Evaluate $\prod_{n=1}^{80}n^{k-n} \pmod{83}$

Evaluate $\displaystyle \prod_{n=1}^{80}n^{80-n} \pmod{83}$.

Attempt:

The product is \begin{align*}\prod_{n=1}^{80}n^{80-n} &= 1^{79} \cdot 2^{78} \cdot 3^{77} \cdots 79^1 \cdot 80^0\\&\equiv -2^{78} \cdot 3^{77} \cdot 4^{77} \cdots 41^{77}\\&\equiv -2 \cdot (1 \cdot 2 \cdots 41)^{77} \\&\equiv -2(1 \cdot 2 \cdots 41)^{77}\pmod{83}\end{align*} Note that $$1^2 \cdot 2^2 \cdot 3^2 \cdots \left(\dfrac{p-1}{2}\right)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod{p}$$ for a prime $p$. Thus for $83$ we find $$(1 \cdot 2 \cdot 3 \cdots 41)^2 \equiv (-1)^{\frac{83+1}{2}} \equiv (-1)^{42} \equiv 1 \pmod{83}.$$ But if $x^2 \equiv 1 \pmod{p}$, then $x \equiv \pm 1 \pmod{p}$. How do we eliminate the case that $1 \cdot 2 \cdots 41 \equiv -1 \pmod{83}$?

• why you start with $k$ and then replace it by $80$ ? – Ahmad May 10 '17 at 23:32
• @Ahmad Sorry, $k$ was $80$. – user19405892 May 10 '17 at 23:33
• the answer is $81$ just for reference. – Dando18 May 10 '17 at 23:34
• by the Wilson theorem $(m!)^2 = (-1)^{m+1} \mod p$ for any odd prime $p=2m+1$, so $(1*2*\cdots *41)^2 =(-1)^{41+1} =1$ – Ahmad May 10 '17 at 23:37
• – heropup May 10 '17 at 23:38

For $\prod_{n=1}^{82} n^{80-n} \mod 83$, we could pair each $n$ with $83-n$: $$n^{80-n} (83-n)^{n-3} \equiv n^{80-n} (-n)^{n-3} \equiv (-1)^{n-3} n^{77}$$ so that $$\prod_{n=1}^{82} n^{80-n} \equiv \prod_{n=1}^{41} (-1)^{n-3} n^{77} \mod 83$$
$\prod_{n=1}^{41} (-1)^{n-3}$ has $20$ factors of $-1$ (one for each even $n$) so it is $1$. $\prod_{n=1}^{41} n \equiv 1 \mod 83$, so $\prod_{n=1}^{41} n^{77} \equiv 1 \mod 83$ as well. Thus $$\prod_{n=1}^{82} n^{80-n} \equiv 1 \mod 83$$ But you're missing the cases $n=81 \equiv -2$ and $n = 82 \equiv -1$, so multiply by $81^{81-80} \equiv 81 \mod 83$ and $82^{82-80} \equiv (-1)^2 \equiv 1 \mod 83$ resulting in $$\prod_{n=1}^{80} n^{80-n} \equiv 81 \mod 83$$
• How do you know that $\prod_{n=1}^{41}n \equiv 1 \pmod{83}$? That was the part I wanted to know. – user19405892 May 11 '17 at 0:04
• Well, it has to be either $1$ or $-1$. By direct computation, it turns out to be $1$. Ah, but see this. – Robert Israel May 11 '17 at 4:03