Getting ready for 2015

Find the remainder when 2015 ! 2015 ! 2015!^{2015!} is divided by 2017.


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.

3 solutions

Ahaan Rungta
Dec 1, 2014

Note, from Wilson's theorem, that 2016 ! 1 ( m o d 2017 ) 2016! \equiv -1 \pmod {2017} . Additionally, if 2015 ! x ( m o d 2017 ) 2015! \equiv x \pmod {2017} , we have 2016 ! x ( m o d 2017 ) 2016! \equiv -x \pmod {2017} , so x 1 x \equiv 1 .

Hence, 2015 ! 2015 ! 1 2015 ! 1 ( m o d 2017 ) . \begin{aligned} 2015!^{2015!} &\equiv 1^{2015!} \\&\equiv \boxed{1} \pmod {2017}. \end{aligned}

Moderator note:

Nice. You should generalize this to ( p 2 ) ! ( p 2 ) ! 1 ( m o d p ) (p-2)!^{(p-2)!} \equiv 1 \pmod {p} for prime p 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)

Cường Huy - 6 years, 6 months ago

Log in to reply

When 2015 ! x 2015!\equiv x , 2016 ! = 2016 × 2015 ! 2016 x = 2017 x x x 2016!=2016\times2015!\equiv2016x=2017x-x\equiv-x , not by the Wilson's Theorem.

Kenny Lau - 6 years, 6 months ago

go find Wilson's theorem. By the way, I couldn't answer it also.

Kenny Santoso - 6 years, 6 months ago

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

Raven Herd - 5 years, 8 months ago

Did the same

Aditya Kumar - 5 years, 1 month ago

[(p-2)!]^a is congruent to 1 mod(p) for arbitrary a, and prime p.

sahil sharma - 4 years, 8 months ago
Jake Lai
Dec 7, 2014

Observe that 2016 2015 ! 2016 | 2015! and that 2017 2017 is a prime number.

By Fermat's little theorem, a p 1 1 m o d p a^{p-1} \equiv 1 \mod p when gcd ( a , p ) = 1 \gcd(a, p) = 1 .

Setting a = 2015 ! a = 2015! and p = 2017 p = 2017 , we have:

2015 ! 2015 ! = ( 2015 ! 2016 ) 2015 ! / 2016 1 2015 ! / 2016 1 m o d 2017 2015!^{2015!} = (2015!^{2016})^{2015!/2016} \equiv 1^{2015!/2016} \equiv \boxed{1} \mod 2017 .

Very well done!!

sahil sharma - 4 years, 8 months ago
Misha Ivkov
Dec 3, 2014

Note that 2017 is prime, so ϕ ( 2017 ) = 2016 \phi(2017)=2016 . Therefore, we find 2015 ! m o d 2016 2015!\mod 2016 , and as 2016 is 2 1008 2*1008 , 2015 ! 0 m o d 2016 2015!\equiv0\mod2016 . Therefore, the modulo is equivalent to 2015 ! 0 m o d 2017 = 1 m o d 2017 2015!^0\mod 2017=1\mod2017 .

Incorrect step in the second line. Rather than 2015 ! 2015 ! 2015 ! 0 m o d 2017 2015!^{2015!} \equiv 2015!^{0} \mod 2017 (which is true but not a valid step), you should have written 2015 ! 2015 ! = ( 2015 ! 2016 ) 2015 ! / 2016 1 2015 ! / 2016 1 m o d 2017 2015!^{2015!} = (2015!^{2016})^{2015!/2016} \equiv 1^{2015!/2016} \equiv 1 \mod 2017 .

Jake Lai - 6 years, 6 months ago

Log in to reply

How is it wrong? If gcd ( A , C ) = 1 \gcd(A,C) = 1 , then by Euler totient function A B m o d C = A B m o d ( ϕ ( C ) ) m o d C A^B \bmod C = A^{B \ \bmod{(\phi(C)) } } \bmod C

Substitute A = 2015 ! , B = 2015 ! , C = 2017 A = 2015!, B = 2015!, C = 2017 gives

2015 ! 2015 ! m o d 2016 m o d 2017 = 201 5 0 m o d 2017 = 1 2015!^{2015! \bmod{2016}} \bmod{2017} = 2015^0 \bmod {2017} = 1

Pi Han Goh - 6 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...