What's that remainder?

My solution uses Wilson's Theorem . Here it is:

Let ${2013 \choose 101}=\frac{2013\times2012\times \ldots \times1913}{(101)!} \equiv c \pmod{101}$ (where $0 \leq c<101$ )

Multiply both sides of the equation by 100!.

By wilson's theorem $100!\equiv -1 \pmod{101}$

$\Rightarrow 2013\times2012\ldots \times(\frac{1919}{101})\ldots \times1913 \equiv c\times100! \equiv -c\pmod{101}$

2013,2012,. . ., 1920 give remainders 94,93, . . ., 1 respectively when divided by 101.

1913,1914, . . .,1918 give remainders 95,96, . . ., 100 respectively on division by 101.

So, ${2013\choose101} \equiv 94! \times19 \times100 \times99 \ldots \times95 \equiv 19\times100! \equiv -c \pmod{101}$ $\Rightarrow c=19$

Therefore $\boxed{{2013\choose101} \equiv 19 \pmod{101}}$

An elementary proof without resorting to Lucas' Theorem follows. First, we claim for all primes $p$ , positive integers $m$ , and integers $0 \le n \le p-1$ , $\binom{mp+n}{p} \equiv \binom{mp}{p} \pmod p.$ For $n = 0$ , the claim is trivially true. For $n \ge 1$ , $\begin{aligned} \binom{mp+n}{p} &= \frac{mp+n}{(m-1)p+n} \binom{mp+n-1}{p} \\ &= \frac{p}{(m-1)p+n} \binom{mp+(n-1)}{p} + \binom{mp+(n-1)}{p}. \end{aligned}$ But since the LHS is an integer, $p$ is prime, and $(m-1)p + n$ cannot divide $p$ under the given conditions, it follows that it must divide $\binom{mp+(n-1)}{p}$ . So the first term on the RHS is divisible by $p$ . Hence $\binom{mp+n}{p} \equiv \binom{mp+(n-1)}{p} \pmod p,$ and induction on $n$ proves our claim. Next, we claim that for positive integers $m$ , $\binom{mp}{p} \equiv m \pmod p.$ For $m = 1$ , the claim is again trivial: $\binom{p}{p} = 1$ . For $m > 1$ , we write $\binom{mp}{p} = \frac{mp}{(m-1)p} \binom{mp-1}{p} = \frac{m}{m-1} \binom{(m-1)p + (p-1)}{p}.$ Thus by the first claim with $n = p-1$ , $\begin{aligned} (m-1) \binom{mp}{p} &\equiv m \binom{(m-1)p+(p-1)}{p} \\ &\equiv m \binom{(m-1)p}{p} \pmod p. \end{aligned}$ By induction on $m$ and recalling that $ax \equiv ay \pmod p$ implies $x \equiv y \pmod p$ for prime $p$ , the result immediately follows. Therefore, we have proved $\binom{mp+n}{p} \equiv m \pmod p,$ and with the choice $m = 19, p = 101, n = 94$ , we find $\binom{2013}{101}$ leaves a remainder of $\boxed{19}$ when divided by $101$ .

First of all, let we see the Lucas theorem : http://ecademy.agnesscott.edu/~lriddle/ifs/siertri/LucasProof.htm

Now, since $2013 = 19. 101^1 + 94.$ $101 = 1. 101^1 + 0$

Then, by Lucas theorem above, we obtain : $m_1 = 19$ $m_0 = 94$ $n_1 = 1$ $n_2 = 0$

$\binom{2013}{101} \equiv \binom{19}{1} . \binom{94}{0} \equiv 19 . 1 \equiv \boxed{19} \pmod{101}$

$\binom{2013}{101} = \frac{2013\cdot2012\cdot...\cdot1919\cdot...\cdot1913}{101\cdot100\cdot...\cdot1}$ . We see that $\frac{1919}{101}=19$ .

Considering the rest of the numerator (without the $1919$ ) $\bmod101$ , we have each of the integers between $1$ and $100$ , inclusive, present. That is, $2013\cdot2012\cdot...\cdot1920\cdot1918\cdot...\cdot1913\equiv$ $94\cdot93\cdot...\cdot1\cdot100\cdot...\cdot95\equiv$ $100!\equiv-1\mod101$ , since for any prime $p$ , $(p-1)!\equiv-1\mod{p}$ by Wilson's Theorem (for more information, see http://en.wikipedia.org/wiki/Wilson's_theorem). Similarly, looking at the rest of the denominator (without the $101$ ), we have $100\cdot99\cdot...\cdot1\equiv100!\equiv-1\mod101$ .

With these in mind, we can solve our problem: $\binom{2013}{101}\equiv$ $\frac{1919}{101}\cdot\frac{2013\cdot2012\cdot...\cdot1920\cdot1918\cdot...\cdot1913}{100\cdot99\cdot...\cdot1}\equiv$ $19\cdot\frac{-1}{-1}\equiv19\mod101$ . Therefore, the remainder when $\binom{2013}{101}$ is divided by $101$ is $\fbox{19}$ .

According to lucas theorem it can be solved.. since $2013 = 19.101 + 94.$ $101 = 1.101 + 0$ applying lucas theorem- $\binom{2013}{101} ≡ \binom{19}{1} . \binom{94}{0} ≡ \boxed{19} (mod 101)$

Note that $2013 = 19 \cdot 101 + 94$ and $101 = 1 \cdot 101 + 0$ . Then, since $101$ is prime, by Lucas' Theorem, we have:

$\dbinom{2013}{101} \equiv \dbinom{19}{1} \cdot \dbinom{94}{0} \equiv 19 \cdot 1 \equiv 19 \pmod{101}$ .

This is a nice solution, the source of the corresponding exercise is Apostol's. For all $p$ , we have that:

${n \choose p} \equiv \left\lfloor \frac{n}{p} \right\rfloor \pmod{p}$

Note that this is a special case of Lucas theorem, which has already been described here.

$\binom{2013}{101}=\frac{2013!}{1912!101!}$ We must find this modulo 11. $\frac{2013!}{1912!101!}\equiv\frac{\prod_{i=1}^{94} i \cdot 19\cdot \prod_{i=1}^6 -i}{100!}\pmod{101}$ Notice the top is equal to $100!\cdot 19$ modulo 101. Now, the $100!$ cancel, and the answer is $\boxed{19}$

We can see that ${2013 \choose 101}=-\prod_{n=1}^{101}\frac{n-2014}{n}$ . Now, we could rearrange this to be $-\frac{\prod_{n=1}^{101} (n-2014)}{\prod_{n=1}^{101} n} \equiv -\frac{\prod_{n=1}^{101} (n+6)}{\prod_{n=1}^{101} n} \pmod{101}$ , but these are not precisely equivalent since $\frac{-1919}{101}\neq\frac{0}{0}$ . So, we can factor this out initially and proceed: $-\frac{-1919}{101}\frac{\prod_{n=1}^{94} (n+6) \prod_{n=96}^{101} (n+6)}{\prod_{n=1}^{100} n} \equiv -\frac{-1919}{101}\frac{\prod_{n=7}^{100} n \prod_{n=102}^{107} n}{\prod_{n=1}^{100} n} \equiv -\frac{-1919}{101}\frac{\prod_{n=1}^{6} n \prod_{n=7}^{100} n}{\prod_{n=1}^{100} n} \equiv \frac{1919}{101} \equiv 19 \pmod{101}$

Here's a solution using the simple lemma:

$ax\equiv ay \pmod b$ $\implies$ $x\equiv y \pmod b$ when $a,b$ are relatively prime.

Proof: $ax\equiv ay \pmod b$ $\implies$ $a(x-y)=bm$ for some integer $m$ , $\implies$ $b\mid a(x-y)$ , since $a,b$ are relatively prime, thus it's clear that $b\mid x-y$ $\implies$ $x\equiv y \pmod b$ . Q.E.D

Now consider the number $100!\binom {2013}{101}$ , which is equal to $2013*2012*...*1920*19*1918*1917*...*1913\equiv 94*93*...*1$ $*19*100*99*...*95\equiv 100!*19 \pmod {101}$ , thus we have $100!\binom {2013}{101}\equiv 100!*19 \pmod {101}$ . Since $101$ is prime, thus $101$ and $100!$ are relatively prime. By the lemma above we have $100!\binom {2013}{101}\equiv 100!*19 \pmod 101$ $\implies$ $\binom {2013}{101}\equiv 19 \pmod {101}$ , which means that the remainder is $19$ .

it can be solved by wid lucas theorem now, 2013=19.101^1+94. 101=1.101^1+0 by Lucas theorem : m1=19 m0=94 n1=1 n2=0 C(2013 101)≡C(19 1).C(94 0) ≡19(mod 101) SO 19 IS ANSWER

According to lucas theorem it can be solved.. since $2013 = 19.101 + 94.$ $101 = 1.101 + 0$ applying lucas theorem- $\binom{2013}{101} ≡ \binom{19}{1} . \binom{94}{0} ≡ 19 (mod 101)$

Note that $\begin{aligned} 1920&\equiv1\pmod{101}\\ 1921&\equiv2\pmod{101}\\ &\vdots\\ 2013&\equiv94\pmod{101}\\ 1913&\equiv95\pmod{101}\\ 1914&\equiv96\pmod{101}\\ &\vdots\\ 1918&\equiv100\pmod{101} \end{aligned}$ Hence $\begin{aligned}\binom{2013}{101}&=\frac{(2013)(2012)\cdots(1913)}{(1)(2)\cdots(101)}\\ &=\frac{1919}{101}\frac{1920}{1}\frac{1921}{2}\cdots\frac{2013}{94}\frac{1913}{95}\cdots\frac{1918}{100}\\ &\equiv(19)(1)(1)\cdots(1)\\ &\equiv\boxed{19}\pmod{101}\end{aligned}$ (Note: all the divisions are valid (mod 101) because the denominators of every fraction, except the first, are coprime to 101.)

Without resorting to fancy combinatoric theorems, we use generating function (1+x)^2013, and consider the coefficient of term x^101, which is 2013C101. Under mod 101, (1+x)^101=1+x^101, for all the coefficients in the middle are divisible by 101. Hence (1+x)^2013 = (1+x^101)^19 (1+x)^94, of which the coefficient of x^101 is 19 by binomial expansion. Namely, the answer is 19.

Only use of-

(n/p) = [n/p] (mod p)

(2013/101)= [2013/101] mod 101

and [2013/101]=19

That's the answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <cstdio>
#include <iostream>
using namespace std;

const int mod = 101;
int memo[2020][2020];

// Evaluate nCr using recursive dynamic program
int choose(int n, int r){
    if(n == 0) return 1;
    if(r == 0 || r == n) return 1;
    if(memo[n][r] != 0) return memo[n][r]-1;
    int ans = choose(n-1, r) + choose(n-1, r-1);
    ans %= mod;
    memo[n][r] = ans+1;
    return ans;
}

int main(){
    cout << choose(2013, 101) << endl;
    return 0;
}

I know it's cheating but.. ahh whatever.

We can prove this using only the fact that elements of Pascal's triangle are the sum of the two elements above.

We have ${2013 \choose 101} = {2012 \choose 100} + {2012 \choose 101}$

Notice that the first term on the LHS is divisible by 101, so we can turn attention to the second. This reasoning is valid until we reach:

${1919 \choose 101} = {1918 \choose 100} + {1918 \choose 101}$

However, we can deal with the first term as follows:

${1918 \choose 100} = {1917 \choose 100} + {1917 \choose 99}$

Again, the first term on the right is divisible by 101, and turning attention to the second, and repeating, we eventually end up with:

${1820 \choose 2} = {1819 \choose 2} + 1819 \equiv 1 \pmod{101}$

Continuing in this way, we see that the problematic terms are ${1918 \choose 100}, {1817 \choose 100},..., {100 \choose 100}.$

There are 19 such terms, all of which are equal $1 \pmod{101}$

$\frac{2013\cdot\dots1912}{1\cdot\dots 1912}$ , top and bottom is a complete residue system, the multiples of $11$ are $19\cdot 101$ and $101$ . They make $19$ when dividing. The rest of the complete residue system cancels out $\bmod 101$ .

We have $\binom{2013}{101} = \frac{2013 \cdot \cdots 1913}{101!} = \frac{2013 \cdot \cdots 1920 \cdot 19 \cdot 1918 \cdot \cdots 1913}{100!}$ after canceling a factor of $101$ from top and bottom.

The numbers $2013, 2012, \ldots, 1921, 1920, 1918, 1917, \ldots, 1913$ left in the numerator run through all of the nonzero congruence classes mod $101$ exactly once. So, modulo $101$ , the numerator is congruent to $19 \cdot 100!$ . Since $101$ is prime, $100!$ is invertible mod $101$ , so it makes sense to rewrite:

$\binom{2013}{101} \equiv 19 (2013 \cdot \cdots 1920 \cdot 1918 \cdot \cdots 1913)(100!)^{-1}$

$\equiv 19(100!)(100!)^{-1} \equiv 19$ mod $101$ .

According to Lucas' theorem since $2013 = 19.101 + 94.$ and $101 = 1.101 + 0$ Therefore
$\binom{2013}{101} ≡ \binom{19}{1} . \binom{94}{0} ≡ 19 (\mod{101})$

My solution uses Wilson's theorem. Here it is:

Let (2013101)=2013×2012×…×1913(101)!≡c(mod101) (where 0≤c<101)

Multiply both sides of the equation by 100!.

By wilson's theorem 100!≡−1(mod101) ⇒2013×2012…×(1919101)…×1913≡c×100!≡−c(mod101) 2013,2012,. . ., 1920 give remainders 94,93, . . ., 1 respectively when divided by 101.

1913,1914, . . .,1918 give remainders 95,96, . . ., 100 respectively on division by 101.

So, (2013101)≡94!×19×100×99…×95≡19×100!≡−c(mod101) ⇒c=19 Therefore (2013101)≡19(mod101)

Since 2013=19.101+94 then according to the lucas theorem we have ${2013 \choose 101} \equiv {19 \choose 1}{94 \choose 0} \equiv 19 \pmod{101}$ Ans: 19.

$\begin{aligned}{2013 \choose 101} &=& \frac{2013 * 2012 * .... * 1919 *...* 1913}{101 * 100 * 99 * 98 * ... * 1} \newline &=& \frac{1919}{101} * \frac{1920}{1}\frac{1921}{2}\frac{1922}{3}...\frac{2013}{94} \frac{1913}{95}...\frac{1918}{100}\end{aligned}$

The first term simplifies: $\frac{1919}{101} = 19$ . The other terms cancel in the arithmetic of the integers mod 101, since each numerator is congruent to the denominator mod 101. So, the product is 19 mod 101.

By Lucas' Theorem, since 101 is prime, this binomial coefficient is equal to a bunch of stuff choose 0 (which is just 1) times 19 choose 1 (modulo 101). This is clearly 19 mod 101.

The question is equivalent to, "What is $\begin{pmatrix}2013\\201\end{pmatrix}$ equivalent to modulo $101$ , as a number from $0$ to $100$ inclusive?"

View this combination as the product $\frac{2013\cdot 2012\cdots1913}{101\cdot100\cdots1} = \frac{2013\cdots1920\cdot1918\cdots1913}{100\cdots1}\cdot\frac{1919}{101}$ .

Note that the first fraction on the right-hand side is equivalent to $1$ modulo $101$ , because the top and bottom each include a number equivalent to $a$ modulo $101$ for each integer $1\leq a\leq 100$ , so their modular products are equal and non-zero.

Then, modulo $101$ , the combination is equivalent to $\frac{1919}{101}=19$ .

We know $2013 \choose 101$ $=\frac {2013 \times 2012 \times... \times 1913}{101 \times 100 \times... \times2 \times 1}$ . In mod 101, we can treat division by 100, 99, 98, etc as multiplication by their multiplicative inverses. Thus, we have $\frac{(2013 \times 2012 \times... \times 1913) \times (100^{-1} \times 99^{-1} \times... \times 2^{-1})} {101}$ . Each value from 1913 to 2013 is a value mod 101. The only value that is divisible by 101 is 1919. Thus, everything cancels until we're left with $\frac {1919} {101} =19$ .

This is a typical problem to be solved by Lucas Theorem. (The proof and explanation of Lucas Theorem is too complicated, I will only write the way to tackle this problem, for more information you can Google it)

$2013=19\cdot101+94$

$101=1\cdot101+0$

Next,

${2013 \choose 101}\pmod{101} \equiv {19 \choose 1}{94 \choose 0}\pmod{101} \equiv 19 \pmod{101}$

So, the remainder of ${2013 \choose 101}$ when divided by $101$ is $19$ .

2013=19.101^1+94. 101=1.101^1+0 by Lucas theorem : m1=19 m0=94 n1=1 n2=0 C(2013 101)≡C(19 1).C(94 0) ≡19(mod 101) SO 19 IS ANSWER

2013=19.101^1+94

101=1.101^1+0

by Lucas theorem:

m1=19

m0=94

n1=1

n2=0

C(2013 101)≡C(19 1).C(94 0)

≡19(mod 101) So 19 is the answer

It means.....2013 c 101 = 2013! _ _ __ 101! (2013-101)! solve this and divide it by 101 which will give the remainder 19

2013=19.101^1+94. 101=1.101^1+0 by Lucas theorem : m1=19 m0=94 n1=1 n2=0 C(2013 101)≡C(19 1).C(94 0) ≡19(mod 101) SO 19 IS ANSWER

by seeing the question we will aply Lucas theorem now 2013=19.1011+94. 101=1.1011+0 Then, by Lucas theorem above, we obtain : m1=19 m0=94 n1=1 n2=0 (2013101)≡(191).(940)≡19.1≡19(mod101)

Since ${2013 \choose 101} = \frac{2013 \cdot 2012 \cdot \ldots \cdot 1913}{101 \cdot 100 \cdot \ldots \cdot 1}$ . Note that $frac{1919}{101} = 19$ . Then note that the numbers from 1913 to 2013 exculding 1919 are 1 to 100 modulo 101. By Wilson's Theorem, ${2013 /choose 101} \equiv \frac{1919 \cdot 100 \cdot 99 \cdot \ldot \cdot 1}{101 \cdot 100 \cdot 99 \cdot \ldot \cdot 1} \equiv \frac{1919}{101} \cdot \frac{-1}{-1} \equiv 19 \pmod {101}$

According to lucas theorem it can be solved.. since $2013 = 19.101 + 94.$ $101 = 1.101 + 0$ applying lucas theorem- $\binom{2013}{101} ≡ \binom{19}{1} . \binom{94}{0} ≡ \boxed{19} (mod 101)$

I am going to use the result that, if p is a prime and m and n are positive integers satisfying m=ap+r , n=bp+s where 0\leq r,s<p, then {m \choose n}≡{a \choose b}{r \choose s}\pmod{p}. Here, m=2013= 101 \times 19 + 94, and n=101 \times 1 + 0. So, {2013 \choose 101}≡{19 \choose 1}{94 \choose 0}≡19 \times 1≡19\pmod{101}. So, the answer is 19.

Using Lucas Theorem (http://en.wikipedia.org/wiki/Lucas'_theorem)

2013=19.101+94. 101=1.101+0

Using Lucas theorem:-

we get, 19 (mod101)