3
$\begingroup$

What is the remainder when the expression $$\prod_{n=1}^{100}(1- n^{2} +n^{4})$$ is divided by $101$?

If $\zeta=\dfrac{-1+\sqrt{-3}}{2}$, then $$1-n^2+n^4=(1-n+n^2)(1+n+n^2)=(-\zeta-n)(-\bar{\zeta}-n)(\zeta-n)(\bar{\zeta}-n).$$ We then have $$\prod_{n=1}^{100}(1-n^2+n^4)\equiv \prod_{n=1}^{100}\big((-\zeta-n)(-\bar{\zeta}-n)(\zeta-n)(\bar{\zeta}-n)\big)\pmod{101}\,.$$ Since $$\prod_{n=1}^{100}(x-n)\equiv x^{100}-1\pmod{101},$$ we obtain $$\prod_{n=1}^{100}(1-n^2+n^4)\equiv\big((-\zeta)^{100}-1\big)\big((-\bar\zeta)^{100}-1\big)\big(\zeta^{100}-1\big)\big(\bar{\zeta}^{100}-1\big)\pmod{101}\,.$$ Since $\zeta^3=1$ and $\bar{\zeta}^3=1$, we get $$(-\zeta)^{100}=\zeta^{100}=\zeta\text{ and }(-\bar\zeta)^{100}=\bar\zeta^{100}=\bar\zeta\,.$$ Therefore, $$\prod_{n=1}^{100}(1-n^2+n^4)\equiv (\zeta-1)^2(\bar{\zeta}-1)^2=\big((1-\zeta)(1-\bar{\zeta})\big)^2\pmod{101}\,.$$ As $$(x-\zeta)(x-\bar{\zeta})=x^2+x+1\,,$$ we get $$\prod_{n=1}^{100}(1-n^2+n^4)\equiv (1^2+1+1)^2=9\pmod{101}\,.$$ Are there other solutions? How do we solve this problem without resorting to complex numbers?

$\endgroup$
6
  • 1
    $\begingroup$ According to WolframAlpha, the remainder is $9$. $\endgroup$
    – an4s
    Jul 9, 2020 at 5:45
  • $\begingroup$ If $f(n) \equiv 1 - n^2 + n^4 \pmod {101}$, then $f(n) = f(-n) = f(101-n)$ since there are only even powers of $n$. $\endgroup$
    – Toby Mak
    Jul 9, 2020 at 5:52
  • 4
    $\begingroup$ Have you seen the answers on AoPS? You should always use Approach0 to search if there are any duplicates, instead of us having to find them for you. $\endgroup$
    – Toby Mak
    Jul 9, 2020 at 5:55
  • 2
    $\begingroup$ Might be able to use: $n^4-n^2+1=\frac{n^6+1}{n^2+1}$ $\endgroup$ Jul 9, 2020 at 5:59
  • 1
    $\begingroup$ Since $100$ is not divisible by $3,$ the values of $n^2+1$ and the values of $n^6+1$ are the same set of values, modulo $101.$ That means we only need to consider the entries when $n^2+1$ is divisible by $101.$ These are $n=10,91.$ This means the remainder is the same as the remainder of $(10^2-10+1)(91^2-91+1)$ which has remainder $1.$ $\endgroup$ Jul 9, 2020 at 6:08

1 Answer 1

6
$\begingroup$

Modulo $101$, the set of values $0^3, 1^3,\dots,100^3$ is a permutation of $0,1,2,\dots,100.$ This is because $101$ is prime and $3$ is not a divisor of $100.$

But $$n^4-n^2+1=\frac{n^6+1}{n^2+1}$$

Now, if $n=10,91$ then $n^2+1$ is divisible by $101.$ The other terms are a permutation, so:

$$\begin{align}\prod_{n=1}^{100} (n^4-n^2+1)&=(10^4-10^2+1)(91^4-91+1)\prod_{n\neq 10,91}\frac{n^6+1}{n^2+1}\\ &\equiv (10^4-10^2+1)((-10)^4-(-10)^2+1)\pmod{101}\\ &\equiv 3\cdot 3=9\pmod{101} \end{align}$$


This works more generally if $p\equiv 5\pmod {12}:$

$$\prod_{n=1}^{p-1}\left(n^4-n^2+1\right)\equiv 9\pmod p$$

If $p\equiv 11\pmod{12},$ the remainder is $1.$

I think when $p\equiv 1\pmod{12},$ the remainder is $0.$

Not sure about $p\equiv 7\pmod{12}.$

$\endgroup$
2
  • 1
    $\begingroup$ Nice! Too bad the question had appeared in AOPS earlier. $\endgroup$ Jul 9, 2020 at 6:31
  • $\begingroup$ The question and the answer, it appears. @JyrkiLahtonen Well, the main hint in the first part here. Oh well, it was fun to solve. $\endgroup$ Jul 9, 2020 at 6:34

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.