From an undisclosed source!

Level 2

What is the largest 3-digit prime factor of ( 2222 1111 ) {2222 \choose 1111} ?

Details and assumptions :

  • You may consult a List of Primes

  • This is not a Computer Science problem; this is a Number Theory problem.


The answer is 739.

Pi Han Goh by Pi Han Goh , 30, Malaysia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Pi Han Goh
Feb 23, 2014

We want to find a prime that divides 2222 ! 2222! and also divides 1111 ! 1111! , so with the binomial coefficient ( 2222 1111 ) {2222 \choose 1111} , that prime must divide 2222 ! 2222! at least 3 times. To determine that largest prime, we just need to search for primes below 2222 3 \frac {2222}{3} , which are 739 , 733 , 727 , 719 , … 739, 733, 727,719, \ldots . By Lucas Theorem, consider modulo 739 739

( 2222 1111 ) ≡ ( 5 372 ) × ( 3 1 ) ≡ 0 ( m o d 739 ) {2222 \choose 1111} \equiv {5 \choose 372} \times {3 \choose 1} \equiv 0 \pmod {739}

So the largest 3-digit prime that divides ( 2222 1111 ) {2222 \choose 1111} is 739 \boxed{739}

2 Helpful 0 Interesting 0 Brilliant 0 Confused

from where there is ( 2222 1111 ) ≡ ( 372 5 ) × ( 3 1 ) ? {2222 \choose 1111} \equiv {372 \choose 5} \times {3 \choose 1} ?

uzumaki nagato tenshou uzumaki - 6 years, 5 months ago

Log in to reply

Lucas' theorem

Pi Han Goh - 6 years, 4 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...