Find the remainder when 2 0 1 5 ! 2 0 1 5 ! is divided by 2017.
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.
Nice. You should generalize this to ( p − 2 ) ! ( p − 2 ) ! ≡ 1 ( m o d p ) for prime p .
I don't understand why "If 2015! = x (mod 2017), then we have 2016! = -x (mod 2017)" ? Can you explain to me? Thanks! (sorry I don't know how to to use Latex)
Log in to reply
When 2 0 1 5 ! ≡ x , 2 0 1 6 ! = 2 0 1 6 × 2 0 1 5 ! ≡ 2 0 1 6 x = 2 0 1 7 x − x ≡ − x , not by the Wilson's Theorem.
go find Wilson's theorem. By the way, I couldn't answer it also.
from Wilson's theorem; (p-1)! is congruent to -1 modulo p which also means that p | (p-1)! +1 which also means that p | (p-1)! - (p-1) consequently p|(p-1) Then we can write, (p-1)! =p q + (p-1); for q belongs to natural numbers (p-2)!=p q(p-1) + `1 thus (p-2)! is congruent to 1 modulo p for a prime p
Did the same
[(p-2)!]^a is congruent to 1 mod(p) for arbitrary a, and prime p.
Observe that 2 0 1 6 ∣ 2 0 1 5 ! and that 2 0 1 7 is a prime number.
By Fermat's little theorem, a p − 1 ≡ 1 m o d p when g cd ( a , p ) = 1 .
Setting a = 2 0 1 5 ! and p = 2 0 1 7 , we have:
2 0 1 5 ! 2 0 1 5 ! = ( 2 0 1 5 ! 2 0 1 6 ) 2 0 1 5 ! / 2 0 1 6 ≡ 1 2 0 1 5 ! / 2 0 1 6 ≡ 1 m o d 2 0 1 7 .
Very well done!!
Note that 2017 is prime, so ϕ ( 2 0 1 7 ) = 2 0 1 6 . Therefore, we find 2 0 1 5 ! m o d 2 0 1 6 , and as 2016 is 2 ∗ 1 0 0 8 , 2 0 1 5 ! ≡ 0 m o d 2 0 1 6 . Therefore, the modulo is equivalent to 2 0 1 5 ! 0 m o d 2 0 1 7 = 1 m o d 2 0 1 7 .
Incorrect step in the second line. Rather than 2 0 1 5 ! 2 0 1 5 ! ≡ 2 0 1 5 ! 0 m o d 2 0 1 7 (which is true but not a valid step), you should have written 2 0 1 5 ! 2 0 1 5 ! = ( 2 0 1 5 ! 2 0 1 6 ) 2 0 1 5 ! / 2 0 1 6 ≡ 1 2 0 1 5 ! / 2 0 1 6 ≡ 1 m o d 2 0 1 7 .
Log in to reply
How is it wrong? If g cd ( A , C ) = 1 , then by Euler totient function A B m o d C = A B m o d ( ϕ ( C ) ) m o d C
Substitute A = 2 0 1 5 ! , B = 2 0 1 5 ! , C = 2 0 1 7 gives
2 0 1 5 ! 2 0 1 5 ! m o d 2 0 1 6 m o d 2 0 1 7 = 2 0 1 5 0 m o d 2 0 1 7 = 1
Problem Loading...
Note Loading...
Set Loading...
Note, from Wilson's theorem, that 2 0 1 6 ! ≡ − 1 ( m o d 2 0 1 7 ) . Additionally, if 2 0 1 5 ! ≡ x ( m o d 2 0 1 7 ) , we have 2 0 1 6 ! ≡ − x ( m o d 2 0 1 7 ) , so x ≡ 1 .
Hence, 2 0 1 5 ! 2 0 1 5 ! ≡ 1 2 0 1 5 ! ≡ 1 ( m o d 2 0 1 7 ) .