9
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ why you start with $k$ and then replace it by $80$ ? $\endgroup$ – Ahmad May 10 '17 at 23:32
  • $\begingroup$ @Ahmad Sorry, $k$ was $80$. $\endgroup$ – user19405892 May 10 '17 at 23:33
  • $\begingroup$ the answer is $81$ just for reference. $\endgroup$ – Dando18 May 10 '17 at 23:34
  • 1
    $\begingroup$ 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$ $\endgroup$ – Ahmad May 10 '17 at 23:37
  • 1
    $\begingroup$ Reference: en.wikipedia.org/wiki/Wilson%27s_theorem#Quadratic_residues $\endgroup$ – heropup May 10 '17 at 23:38
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How do you know that $\prod_{n=1}^{41}n \equiv 1 \pmod{83}$? That was the part I wanted to know. $\endgroup$ – user19405892 May 11 '17 at 0:04
  • $\begingroup$ Well, it has to be either $1$ or $-1$. By direct computation, it turns out to be $1$. Ah, but see this. $\endgroup$ – Robert Israel May 11 '17 at 4:03

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.