If ( 2 9 9 9 2 9 9 9 9 ) is divided by 2 9 9 9 9 , the remainder is N . What is the last three digits of N ?
Details and assumptions : You may use the fact that 2 9 9 9 is prime.
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.
Oh nice trick of writing 1 / p = p 8 / p 9 . This is simpler than how I've solved it (which I've already forgotten). Beautiful!
Log in to reply
Thanks. There's actually a basic property of congruences I could have used to get the congruence modulo p 9 directly: x ≡ y ( m o d m ) ⟹ a x ≡ a y ( m o d a m ) 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 ;-)
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!
Problem Loading...
Note Loading...
Set Loading...
For any prime p , ( p − 1 ) ! ≡ 0 ( m o d p ) , so ( p − 1 p 9 − 1 ) = ( p − 1 ) ! ( p 9 − 1 ) ( p 9 − 2 ) ⋯ ( p 9 − ( p − 1 ) ) ≡ ( p − 1 ) ! ( p − 1 ) ! ≡ 1 ( m o d p )
It follows that p 9 1 ( p p 9 ) = p 9 1 ⋅ ( p p 9 ⋅ ( p − 1 p 9 − 1 ) ) = p 1 ⋅ ( p − 1 p 9 − 1 ) = ⌊ p 1 ( p − 1 p 9 − 1 ) ⌋ + p 1 = ⌊ p 1 ( p − 1 p 9 − 1 ) ⌋ + p 9 p 8 so that ( p p 9 ) ≡ p 8 ( m o d p 9 ) .
Using p = 2 9 9 9 yields ( 2 9 9 9 2 9 9 9 9 ) ≡ 2 9 9 9 8 ( m o d 2 9 9 9 9 ) ⟹ N = 2 9 9 9 8 ≡ ( − 1 ) 8 = 1 ( m o d 1 0 0 0 ) showing that the last three digits of N are 0 0 1