0
$\begingroup$

How can I find the remainder when $\displaystyle\binom{2018}{1009}$ is divided by $ 2017^2?$

My Approach:
I have used Lucas' theorem Extension here,that is $$\binom{n}{m} \equiv \frac{P}{Q}(\mod p^f)$$ $$\text{where},P=\prod_{i=0}^{s-f+1} \binom{n_i+n_{i+1}p+ \dots+n_{i+f-1}p^{f-1}}{m_i + m_{i+1}p+ \dots+ m_{i+f-1}p^{f-1}}$$ $$\& \space Q=\prod_{i=1}^{s-f+1} \binom{n_i+n_{i+1}p+ \dots+n_{i+f-2}p^{f-2}}{m_i + m_{i+1}p+ \dots+ m_{i+f-2}p^{f-2}}$$ so applying Lucas' theorem Extension in this problem: $$\text{We can write : } \binom{2018}{1009}= \binom{1 \times 2017 \quad \quad 1 \times 2017^0}{0 \times 2017 \quad \quad 1009 \times 2017^0}$$ $$\implies s=1,f=2$$ $$\therefore P= \prod_{i=0}^{0} \binom{n_i+n_{i+1}p}{m_i + m_{i+1}p} \space \& \space Q= \prod_{i=1}^{0} \binom{n_i}{m_i }$$ $$\implies P= \binom{1 \times 2017 \quad \quad 1 \times 2017^0}{0 \times 2017 \quad \quad 1009 \times 2017^0} \space \& \space Q= 1$$ so again we are getting: $$\binom{2018}{1009}=\frac{\binom{2018}{1009}}{1} \mod (2017^2)$$

Thus, ${\color{red}{\text{NO IMPROVEMENT}}}$
so how can i evaluate its remainder??
and if possible then how can we modify this process to get the answer? please help...

$\endgroup$
4
$\begingroup$

Note that

$$\binom{2018}{1009}=\frac{2018!}{1009!^2}=2018\cdot 2017\frac{2016!}{1009!^2}\equiv x \pmod{2017^2}\\\iff 2018\cdot \frac{2016!}{1009!^2}\equiv \frac{x}{2017} \pmod{2017}$$

and since

$$(p-1)!\equiv -1 \pmod{p}$$

$$\left[\left(\frac{p-1}{2}\right)!\right]^{2}\equiv (-1)^{\frac{p+1}{2}}\pmod{p}$$

we have that $$ \frac{x}{2017}\equiv2018\frac{2016!}{1009!^2} \equiv \frac{2016!}{1009^2\cdot1008!^2}\equiv \frac{1}{1009^2} \iff \frac{x\cdot 1009^2}{2017}\equiv 1 \pmod{2017}$$

note that

$$1009^2=\left( \frac{2017+1}{2}\right)^2=\frac14(2017^2+2\cdot2017+1)\equiv\frac14 \pmod{2017}$$

thus

$$\frac{x\cdot 1009^2}{2017}\equiv 1 \iff \frac{x}{4\cdot 2017}\equiv 1 \pmod{2017}\iff x \equiv 8068 \pmod{2017^2}$$

$\endgroup$
  • $\begingroup$ How ((2016!)/((1009^2)*((1008!)^2)) == 1/(1009^2) ? ,please explain $\endgroup$ – Suresh Jan 21 '18 at 3:57
  • $\begingroup$ @user9198116 $2016!\equiv -1$ for wilson theorem and $(1008!)^2\equiv-1$ for math.stackexchange.com/questions/131175/… $\endgroup$ – gimusi Jan 21 '18 at 6:51
3
$\begingroup$

Hint: make use of the binomial identity $${2n\choose n} =2^n\frac{1\times 3\times 5\times\cdots\times (2n-1)}{n!}$$

$\endgroup$

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.