Wilson's Theorem

Wilson’s Theorem says 40! ≡ 40 mod 41. Note that 4763 = 41 x 43. Now, we want to calculate 40! mod 43. Note that 43 is prime also, so we know that 42! = 42 mod 43.

42! ≡ (40!)(-2)(-1) ≡ 42 (mod 43) 2(40!) ≡ 42 (mod 43), we know that 2-1 ≡ 22 (mod 43). So, multiply this through by 22: 22(2)(40!) ≡ 22(-1) (mod 43) 40! ≡ -22 (mod 43) 40! ≡ 21 (mod 43)

So, now we have two equations:

40! ≡ -1 (mod 41) 40! ≡ 21 (mod 43)

Use the Chinese Remainder Theorem to solve for 40! mod 1763. Let x = 40! So, we have:

x ≡ -1 (mod 41) x ≡ 21 (mod 43)

43x ≡ -43 (mod 1763) 41x ≡ 861 (mod 1763)

Since 43 ≡ 2 mod 41, we have 43-1≡ 21 mod 41. Since 41≡ -2 mod 43, we have 41-1 ≡ 21 mod 43.

Multiply both equations through by 21:

903x ≡ -903 (mod 1763) 861x ≡ 18081 (mod 1763)

1764x ≡ 17178 (mod 1763)
x ≡ 1311 (mod 1763)

Thus, 1311 is our desired remainder.

Step 1: 1763 = 41 43. both numbers are prime. now, 40! ≡ 40 (mod41) and 42! ≡ 42 (mod43). we need both to be 40! so the first is set, the second needs a little work. 42! ≡ 42 (mod43) 42 41 40! ≡ 42 (mod43) 41 40! ≡ 1 (mod43) (-2)*40! ≡ -42 (mod43) so 40! ≡ 21 (mod43).

Step 2: let 40! ≡ K (mod 1763), where K is bigger or equal to 1 and smaller than 1763. K ≡ 40 (mod41) K ≡ 21 (mod43) now, using the Chinese Remainder Theorem, we get K ≡ 1311 (mod1763).