To find $72^{1001} \mod 31$, we can use modular arithmetic techniques, such as Fermat's Little Theorem and exponentiation by squaring, to simplify the calculation.

Step 1: Simplifying the base using modular reduction

First, reduce the base $72 \mod 31$:

$72 \mod 31 = 72 - (2 \times 31) = 72 - 62 = 10$

Thus, $72 \equiv 10 \mod 31$.

Now the problem becomes finding:

$10^{1001} \mod 31$

Step 2: Applying Fermat's Little Theorem

Fermat's Little Theorem states that if $p$ is a prime number and $a$ is an integer not divisible by $p$, then:

$a^{p-1} \equiv 1 \mod p$

Here, $p = 31$ and $a = 10$, so:

$10^{30} \equiv 1 \mod 31$

Now, we can reduce the exponent $1001 \mod 30$ to simplify the power:

$1001 \mod 30 = 1001 - (33 \times 30) = 1001 - 990 = 11$

Thus, $10^{1001} \equiv 10^{11} \mod 31$.

Step 3: Computing $10^{11} \mod 31$

Now, we calculate $10^{11} \mod 31$ using exponentiation by squaring:

$10^2 = 100 \quad \text{and} \quad 100 \mod 31 = 100 - (3 \times 31) = 100 - 93 = 7$

$10^4 = (10^2)^2 = 7^2 = 49 \quad \text{and} \quad 49 \mod 31 = 49 - 31 = 18$

$10^8 = (10^4)^2 = 18^2 = 324 \quad \text{and} \quad 324 \mod 31 = 324 - (10 \times 31) = 324 - 310 = 14$

Now, using this to compute $10^{11}$:

$10^{11} = 10^8 \times 10^2 \times 10 = 14 \times 7 \times 10 = 980$

Finally, reduce $980 \mod 31$:

$980 \mod 31 = 980 - (31 \times 31) = 980 - 961 = 19$

Final Answer:

Thus, $72^{1001} \equiv 19 \mod 31$.

Let me know if you'd like further details or have any questions! Here are some related questions:

1. How can Fermat's Little Theorem be applied to other moduli?
2. What are the steps for exponentiation by squaring in modular arithmetic?
3. Can modular arithmetic be applied in cryptography?
4. How would this change if we used a different base for the exponent?
5. What happens when the base is divisible by the modulus?

Tip: Always reduce the base modulo $n$ first—it simplifies calculations drastically!