How to prove that $50^{44}+30! \cdot44^{50}-24 $ is divisible by $31$? I am struggling with this example. This is a new topic for me. I would really appreciate some hints to understand it. I need part a) and b) to conclude the excercise.
I was thinking about Fermat, Euler or Wilson theorems but I am not sure if it is correct, of course I can use properties of congruences in number theory.
Part a): show that $50^{44}+30! \cdot 44^{50}-24 $ is divisible by $31$
Part b) : Conclude that $ (50^{44}+30!\cdot 44^{50})^{\varphi(31)} \equiv 1 \pmod{ 31}$
 A: Here's a handful of hints:
$50^{44} = 2^{44}5^{88}$
$44^{50} = 2^{100}11^{50}$
$2^5\equiv 1 \pmod{31}$
$5^3 \equiv 1 \pmod{31}$
$11^2 \equiv -3 \pmod{31}$
A: \begin{align}
50^{44} + 30! \cdot 44^{50} &\equiv 50^{44} - 44^{50} \pmod{31}, \text{ By Wilson's Theorem } \\
&\equiv 2^{44} \cdot 5^{88} - 2^{100}\cdot 11^{50} \pmod{31} \\
&\equiv 2^{14}\cdot 5^{28} - 2^{10} \cdot 11^{20} \pmod{31}\text{, By Fermat's little Theorem } \\
&\equiv 2^{4} \cdot 5 - (-3)^{10} \pmod{31}, \\
&\equiv 2^4 \cdot 5 - 3^{10} \pmod{31} \\
&\equiv 2^4  \cdot 5 - 3^{3\times 3}\cdot 3 \pmod{31} \\
&\equiv 2^4 \cdot 5 - (-4)^3 \cdot 3 \pmod{31} \\
&\equiv 2^4 (5+12) \pmod{31} \\
&\equiv 2^4 (2^4+1) \pmod{31}
\\ &\equiv2^8  + 2^4 \pmod{31} \\
&\equiv 2^3 + 2^4 \pmod{31} \\
&\equiv 24 \pmod{31}
\end{align}
A: Notice we can use Fermat's little theorem to reduce the exponents using mod order reduction, based on these values:
$\  \color{#0a0}{2^5\equiv 1},\,$ $\, \color{#c00}{5^3\equiv 1},\,$ $\, \color{#90f}{11^3}\equiv 11(-3) \equiv \color{#90f}{-2},\,$ yielding
$$\begin{align} 
   \bmod 31\!:\quad\     & 50^{44}\!+30! \cdot 44^{50}\\[,2em] 
\equiv\ & 50^{14}\ \ \ \, -\,\ \ \ 44^{20}\qquad\ \ {\rm by}\ \ 30!\equiv -1\,\ {\rm by\ Wilson}\\[,2em]
\equiv\ &\color{#0a0}{2^{14}} \cdot \color{#c00}{5^{28}}-\color{#0a0}{2^{40}} \cdot \color{#90f}{11^{20}}\\[.3em]
\equiv\ &\ \ \ \ \ \frac{\color{#c00}{5}}{\color{#0a0}2}\,\ -\,\ \color{#0a0}1\cdot \color{#90f}{\frac{(-2)^{7}}{11} \ \ \ \text{by (*) below}}\\[.3em]
\equiv\ &\ \ \ \ \frac{\color{}{36}}{2}\ \ \ \ \ +\ \ \ \ \ \frac{\color{#90f}{2^{2}}}{11}\quad\ \ {\rm by}\ \ \color{#0a0}{2^5\equiv 1}\\[.3em]
\equiv\ &\ \ \ \ 18\ \ +\ \ \frac{\color{}{4+62}}{11}\\
\equiv\ &\ \ \ \ 24
\end{align}\!\!\!$$
$\color{#90f}{\text{(*)}}\,$ we used $\ \color{#90f}{11^3 = -2}\ \, \smash{\overset{\Large x^{7}\!}\Longrightarrow}\ 11^{21} \equiv (-2)^7\!\Rightarrow \color{#90f}{11^{20}\equiv (-2)^7/11},\ $ then in the next two lines we twiddle the fraction numerators by adding (or subtracting) small multiples of the modulus so to make the quotient exact.
Part b) is just FLT again.
Check here to see how modular fractions work.
