Factorial Division Remainder

$5183=71\times 73$

Using Wilson's Theorem :

$\displaystyle \color{royalblue}{\textbf{Wilson's theorem: }} \boxed{70!\equiv -1\pmod {71}}$

$\displaystyle \color{royalblue}{\textbf{Wilson's theorem: }} 72\cdot 71\cdot 70!\equiv -1\pmod {73}$

$\displaystyle \implies (-1)(-2)\cdot 70!\equiv -1\equiv 72\pmod {73}\stackrel{:2}{\implies} \boxed{70!\equiv 36\pmod {73}}$

Using Extended Euclidean Algorithm we know that

$\displaystyle \begin{cases}73=71+2\\ 71=2(35)+1\end{cases}$

$\displaystyle \implies 1=71-2(35)=71-(73-71)(35)=71(36)+73(-35)$

Or subtract consecutive equations:

$73=73(1)+71(0)$

$71=73(0)+71(1)$

$2=73(1)+71(-1)$

$1=73(-35)+71(36)$

See Chinese Remainder theorem (CRT).

$\color{royalblue}{\textbf{answer}}\equiv 36\cdot 71(36)+(-1)\cdot 73(-35)\equiv \boxed{1277}\pmod {5183}$

Simply a python code that prints the answer

ans

Sorry for not following the note, but I am learning programming so added this one :P

70!=k.71+70 . We know that p((p-3)!-(p-1)/2) with p prime, or 70!=t.73+36 and so 70!=m.5183 + 1277.

For simplicity, let $r$ be the unknown remainder and $n=5183$ . Let's sharpen our pencils and do this: $$

1. Factor $n<75^2$ : We only need to check the first 21 primes smaller than 75. The simple divisibility rules for 2; 3; 5; 11 all fail, so we begin with the largest primes in the list to get lucky and find $n=71\cdot 73$ $$

2. We may use the Chinese Remainder Theorem, because $\gcd(71,\:73)=1$ : $\begin{aligned} r&\equiv 70!\mod n&&&\Leftrightarrow &&&&\begin{aligned} r&\equiv 70!\mod 71\\[.25em] r&\equiv 70!\mod 73 \end{aligned} \end{aligned}$

3. For the first factorial, we use Wilson's Theorem directly. For the second factorial, we are missing the factors $71;\:72$ , so we need their inverses. We notice $(-72)\equiv1 \mod 73$ , and find $\red{36}\cdot 71\equiv 1\mod 73$ using Euclid's Algorithm: $\begin{aligned} \begin{array}{r|r|r|r} k & r_k & a_k & x_k\\\hline -2 & 73 & & \\ -1 & 71 & & \\ 0 & 2 & 1 & \red{36} \\ 1 & 1 & 35 & -\blue{35} \\ 2 & \underline{\underline{0}} & 2 & 1 \end{array}&&&&\Rightarrow&&&& 1 &= \red{36}\cdot 71-\blue{35}\cdot 73&&&&&\left|\quad\begin{aligned} 70!&\equiv -1\mod 71\\[.25em] 70!&\equiv 70!\cdot (\red{36}\cdot 71)\cdot (-72)\equiv 72!\cdot(-36)\\ &\equiv (-1)\cdot (-36)\equiv 36\mod 73 \end{aligned}\right. \end{aligned}$

4. We combine our system of congruences to get a single general linear diophantine equation: $\begin{aligned} \begin{aligned} r&\equiv -1\mod 71\\[.25em] r&\equiv 36\mod 73 \end{aligned}&&&&\Leftrightarrow&&&&\left.\begin{aligned} r&= -1 + 71x\\[.25em] r&= 36 + 73y \end{aligned}\right\} && 37&=71x-73y, &&& x,\:y&\in\mathbb{Z} \end{aligned}$ With the result of Euclid's Algorithm earlier, we can directly write down all solutions. $(*)\:\:k\rightarrow k-18$ keeps the result small: $\begin{aligned} \begin{pmatrix}x\\y\end{pmatrix}&=\begin{pmatrix} \red{36}&73\\ \blue{35}& 71 \end{pmatrix}\begin{pmatrix}37\\k\end{pmatrix}\underset{(*)}{=}\begin{pmatrix} 18&73\\ 17& 71 \end{pmatrix}\begin{pmatrix}1\\k\end{pmatrix},& k&\in\mathbb{Z}&&&\Rightarrow &&&& r&=-1+71x=\boxed{1277}+nk,&k&\in\mathbb{Z} \end{aligned}$