Powered Prime Choose Prime Modulo Powered Prime.

Level 2

If ( 299 9 9 2999 ) {2999^9 \choose 2999} is divided by 299 9 9 2999^9 , the remainder is N N . What is the last three digits of N N ?

Details and assumptions : You may use the fact that 2999 2999 is prime.


The answer is 1.

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

Brian Moehring
Aug 23, 2018

For any prime p , p, ( p 1 ) ! ≢ 0 ( m o d p ) , (p-1)! \not\equiv 0 \pmod{p}, so ( p 9 1 p 1 ) = ( p 9 1 ) ( p 9 2 ) ( p 9 ( p 1 ) ) ( p 1 ) ! ( p 1 ) ! ( p 1 ) ! 1 ( m o d p ) \binom{p^9 - 1}{p-1} = \frac{(p^9-1)(p^9-2)\cdots(p^9-(p-1))}{(p-1)!} \equiv \frac{(p-1)!}{(p-1)!} \equiv 1 \pmod{p}

It follows that 1 p 9 ( p 9 p ) = 1 p 9 ( p 9 p ( p 9 1 p 1 ) ) = 1 p ( p 9 1 p 1 ) = 1 p ( p 9 1 p 1 ) + 1 p = 1 p ( p 9 1 p 1 ) + p 8 p 9 \begin{aligned} \frac{1}{p^9}\binom{p^9}{p} &= \frac{1}{p^9} \cdot \left(\frac{p^9}{p}\cdot \binom{p^9-1}{p-1}\right) \\ &= \frac{1}{p} \cdot \binom{p^9-1}{p-1} \\ &= \left\lfloor\frac{1}{p} \binom{p^9-1}{p-1}\right\rfloor + \frac{1}{p} \\ &= \left\lfloor\frac{1}{p} \binom{p^9-1}{p-1}\right\rfloor + \frac{p^8}{p^9} \end{aligned} so that ( p 9 p ) p 8 ( m o d p 9 ) . \binom{p^9}{p} \equiv p^8 \pmod{p^9}.

Using p = 2999 p=2999 yields ( 299 9 9 2999 ) 299 9 8 ( m o d 299 9 9 ) \binom{2999^9}{2999} \equiv 2999^8 \pmod{2999^9} N = 299 9 8 ( 1 ) 8 = 1 ( m o d 1000 ) \implies N = 2999^8 \equiv (-1)^8 = 1 \pmod{1000} showing that the last three digits of N N are 001 \boxed{001}

Oh nice trick of writing 1 / p = p 8 / p 9 1/p = p^8 /p^9 . This is simpler than how I've solved it (which I've already forgotten). Beautiful!

Pi Han Goh - 2 years, 9 months ago

Log in to reply

Thanks. There's actually a basic property of congruences I could have used to get the congruence modulo p 9 p^9 directly: x y ( m o d m ) a x a y ( m o d a m ) x\equiv y \pmod{m} \implies ax\equiv ay \pmod{am} but for some reason my tired mind is never able to think of such properties, so I end up re-inventing the wheel a lot.

Either way, it was a nice problem. I don't know how long ago you posted it, but it seemed a shame to leave it without a solution ;-)

Brian Moehring - 2 years, 9 months ago

Log in to reply

Easily 3 years ago! It's too bad there's no timestamp on when our problems were posted.

I posted this because I've found it in an undergraduate NT textbook. If I recall correctly, their solution is much much less elegant than yours!

Pi Han Goh - 2 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...