You Can't Do That With Wilson's Theorem!

Wilson Junior wants to determine the least positive integer N N such that N 82 ! ! m o d 83 N \equiv 82!!\, \bmod \,83 . He applied Wilson's theorem as follows: N ( 82 ! ) ! m o d 83 ( 1 ) ! m o d 83 1 m o d 83 82 m o d 83. \begin{array}{rl} N &\equiv \, (82!)! \,\bmod \,83\\ &\equiv \, -(1)!\,\bmod \,83\\ &\equiv \, -1\,\bmod \,83\\ &\equiv \, 82 \bmod 83. \end{array} We can see that the calculation of 82 ! ! 82!! by setting parentheses in the starting steps is fallacious. So, what is the true, least positive value of N ? N?


Notation: ! ! !! denotes the double factorial notation. For example, 10 ! ! = 10 × 8 × 6 × 4 × 2 10!!=10\times8\times6\times4\times2 .


The answer is 82.

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
Jun 14, 2018

Partial solution :

Note that N 82 ! ! 2 41 41 ! ( m o d 83 ) N \equiv 82!! \equiv 2^{41} \cdot 41! \pmod{83} and 83 83 is prime, so in particular N 2 2 82 ( 41 ! ) 2 ( m o d 83 ) 1 ( 41 ! ) 2 ( m o d 83 ) by Fermat’s Little Theorem 41 ! ( 1 ) 41 ( 1 ) ( 2 ) ( 41 ) 41 ! ( 1 ) ( 82 ) ( 81 ) ( 42 ) ( 1 ) 82 ! ( m o d 83 ) ( 1 ) ( 1 ) ( m o d 83 ) by Wilson’s theorem 1 ( m o d 83 ) \begin{aligned}N^2 &\equiv 2^{82} \cdot (41!)^2 \pmod{83}& \\ &\equiv 1 \cdot (41!)^2 \pmod{83} & \text{ by Fermat's Little Theorem} \\ &\equiv 41! \cdot (-1)^{41} (-1)(-2)\cdots (-41) \equiv 41! \cdot (-1) \cdot (82)(81)\cdots(42) \equiv (-1)\cdot 82! \pmod{83} & \\ &\equiv (-1) \cdot (-1) \pmod{83} & \text{ by Wilson's theorem} \\ &\equiv 1 \pmod{83} \end{aligned}

Then using the fact 83 83 is prime once more, N 2 1 ( m o d 83 ) N ± 1 ( m o d 83 ) N^2 \equiv 1 \pmod{83} \Rightarrow N \equiv \pm 1 \pmod{83}

Therefore the only two possible answers are N = 1 N=1 or N = 82 N=82 . I don't know yet how to show N N is not 1 1 (other than brute force).

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...