If 9 9 0 0 0 0 0 9 5 6 ! = x m o d 9 9 0 0 0 0 0 9 5 9 , find x .
Hint : You may use the fact that 9900000959 is prime.
Please don't use computer to solve this problem.
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.
you can add this extension to the wiki @ calvin lin
We know by Wilson's Theorem that for any prime p ,
( p − 1 ) ! ≡ − 1 m o d p
Since 9 9 0 0 0 0 0 9 5 9 is prime, we have
( 9 9 0 0 0 0 0 9 5 9 − 1 ) ! ≡ − 1 m o d 9 9 0 0 0 0 0 9 5 9 or 9 9 0 0 0 0 0 9 5 8 ! ≡ 9 9 0 0 0 0 0 9 5 8 m o d p
It can be observed that 9 9 0 0 0 0 0 9 5 8 ! = 9 9 0 0 0 0 0 9 5 8 × 9 9 0 0 0 0 0 9 5 7 × 9 9 0 0 0 0 0 9 5 6 !
Also, 9 9 0 0 0 0 0 9 5 8 ≡ − 1 m o d 9 9 0 0 0 0 0 9 5 9 and 9 9 0 0 0 0 0 9 5 7 ≡ − 2 m o d 9 9 0 0 0 0 0 9 5 9
So,
9 9 0 0 0 0 0 9 5 8 × 9 9 0 0 0 0 0 9 5 7 × 9 9 0 0 0 0 0 9 5 6 ! ≡ ( − 1 ) × ( − 2 ) × 9 9 0 0 0 0 0 9 5 6 ! ≡ 9 9 0 0 0 0 0 9 5 8 m o d 9 9 0 0 0 0 0 9 5 9
Thus,
9 9 0 0 0 0 0 9 5 6 ! ≡ ( − 1 ) × ( − 2 ) 9 9 0 0 0 0 0 9 5 8 ≡ 4 9 5 0 0 0 0 4 7 9 m o d 9 9 0 0 0 0 0 9 5 9
From wilsons theorem it follows that, the answer is 2 − 1 modulo that prime we can easliy find the modular inverse of 2 here.Simply, 2 p r i m e + 1 for that minus sign we subtract the modular inverse of 2 from that prime which results in 4950000479
Problem Loading...
Note Loading...
Set Loading...
ok here's something little i derived (p-3)! = (p-1)/2 mod p so applying it putting p=9900000959 in it we get 4950000479