×

# Gargantuan Prime

Let p be the largest prime less than 2013 for which

$$N = 20 + p^{p^{p + 1} - 13}$$

is also a prime. Find the remainder when N is divided by $$10^4$$.

Note by Mharfe Micaroz
4 years, 7 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Obviously $$p=2011$$

So we want to find

$$(20 + 2011^{2011^{2012}-13} ) \bmod{10000}$$

Apply Euler's totient Function, $$\phi (10000) = 10000(1- \frac {1}{2})(1 - \frac {1}{5} ) = 4000$$

$$2011^{2012} \bmod{4000}$$

$$= (2011^2 \bmod{4000})^{1006} \bmod{4000}$$

$$= 121^{1006} \bmod{4000}$$

$$= (121^2 \bmod{4000})^{503} \bmod{4000}$$

$$= 2641^{503} \bmod{4000}$$

$$= ( 2641^{502} \cdot 2641 ) \bmod{4000}$$

$$= ( (2641^2 \bmod{4000})^{251} \cdot 2641 ) \bmod{4000}$$

$$= ( 2881^{251} \cdot 2641 ) \bmod{4000}$$

$$= ( 2881^{250} \cdot 2641 \cdot 2881) \bmod{4000}$$

$$= ( (2881^2 \bmod{4000})^{125} \cdot 2641 \cdot 2881) \bmod{4000}$$

$$= ( 161^{125} \cdot 2641 \cdot 2881) \bmod{4000}$$

$$= ( 161^{125} \cdot 2641 \cdot 2881) \bmod{4000}$$

$$= ( 161^{124} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}$$

$$= ( (161^2 \bmod{4000})^{62} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}$$

$$= ( 1921^{62} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}$$

$$= ( (1921^2 \bmod{4000})^{31} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}$$

$$= ( 2241^{31} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}$$

$$= ( 2241^{30} \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241) \bmod{4000}$$

$$= ( (2241^2 \bmod{4000})^{15} \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241) \bmod{4000}$$

$$= ( 2081^{15} \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241) \bmod{4000}$$

$$= ( 2081^{14} \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081) \bmod{4000}$$

$$= ( (2081^2 \bmod{4000})^7 \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081) \bmod{4000}$$

$$= ( 2561^7 \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081) \bmod{4000}$$

$$= ( 2561^6 \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081 \cdot 2561) \bmod{4000}$$

$$= ( (2561^2 \bmod{4000})^3 \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081 \cdot 2561) \bmod{4000}$$

$$= ( 2721^3 \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081 \cdot 2561) \bmod{4000}$$

$$= ( 2721^2 \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081 \cdot 2561 \cdot 2721) \bmod{4000}$$

$$= ( (2721^2 \bmod{4000} ) \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081 \cdot 2561 \cdot 2721) \bmod{4000}$$

$$= ( 3841 \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241 \cdot 2081 \cdot 2561 \cdot 2721) \bmod{4000}$$

$$= ( (3841 \cdot 2641 \bmod{4000}) \cdot (2881 \cdot 161 \bmod{4000}) \cdot (2241 \cdot 2081 \bmod{4000}) \cdot (2561 \cdot 2721 \bmod{4000})) \bmod{4000}$$

$$= ( 81 \cdot 3841 \cdot 3521 \cdot 481) \bmod{4000}$$

$$= ( (81 \cdot 3841 \bmod{4000}) \cdot (3521 \cdot 481 \bmod{4000}) \bmod{4000}$$

$$= (3121 \cdot 1601) \bmod{4000}$$

$$= 721$$

$$(2011^{2012} - 13 ) \bmod{4000} = 708$$

So,

$$(20 + 2011^{2011^{2012}-13} ) \bmod{10000}$$

$$\large = (20 + 2011^{(2011^{2012}-13) \bmod{4000}} ) \bmod{10000}$$

$$= (20 + 2011^{708} ) \bmod{10000}$$

Notice that by Binomial Theorem

$$2011^{708} = (2000 + 11)^{708} = 11^{708} + 11^{707} \cdot 2000 + 10000A$$, for some integer $$A$$

$$\Rightarrow 2011^{708} \bmod{10000} = (11^{708} + 11^{707} \cdot 2000 ) \bmod 10000$$

Continue:

$$= (20 + (11^{708} + 11^{707} \cdot 2000 ) ) \bmod{10000}$$

$$= (20) + (11^{708} \bmod 10000) + (11^{707} \cdot 2000 \bmod{10000})$$

Since $$11^{707}$$ ends with $$1$$ because $$1 \cdot 1 \cdot \ldots \cdot 1 = 1$$, then the last four digits of $$11^{707} \cdot 1000$$ is $$1000$$, or the last four digits of $$11^{707} \cdot 2000$$ is $$2000$$ $$\Rightarrow (11^{707} \cdot 2000 \bmod{10000}) = 2000$$

Continue:

$$= (20) + (11^{708} \bmod{10000}) + (2000)$$

$$= (2020) + (11^{708} \bmod{10000})$$

$$= (2020) + ( (11^4 \bmod 10000)^{177} \bmod{10000})$$

$$= (2020) + ( 4641^{177} \bmod{10000})$$

$$= (2020) + ( 4641^{177} \bmod{10000})$$

$$= (2020) + ( 4641^{176} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( (4641^2 \bmod{10000})^{88} \cdot 4641 \bmod{10000}$$

$$= (2020) + ( (-1119)^{88} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( ((-1119)^2 \bmod{10000})^{44} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( 2161^{44} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( (2161^2 \bmod{10000})^{22} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( (-79)^{22} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( ((-79)^2 \bmod{10000})^{11} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( 6241^{11} \cdot 4641 \bmod{10000})$$

$$= (2020) + ( 6241^{10} \cdot 4641 \cdot 6241 \bmod{10000})$$

$$= (2020) + ( (6241^2 \bmod{10000})^5 \cdot 4641 \cdot 6241 \bmod{10000})$$

$$= (2020) + ( 81^5 \cdot 4641 \cdot 6241 \bmod{10000})$$

$$= (2020) + ( 81^4 \cdot 4641 \cdot 6241 \cdot 81 \bmod{10000})$$

$$= (2020) + ( (81^2 \bmod{10000})^2 \cdot 4641 \cdot 6241 \cdot 81 \bmod{10000})$$

$$= (2020) + ( 6561^2 \cdot 4641 \cdot 6241 \cdot 81 \bmod 10000)$$

$$= (2020) + ( (6561^2 \bmod{10000}) \cdot 4641 \cdot 6241 \cdot 81 \bmod{10000})$$

$$= (2020) + ( 6721 \cdot 4641 \cdot 6241 \cdot 81 \bmod{10000}$$

$$= (2020) + ( (6721 \cdot 4641 \bmod{10000}) \cdot (6241 \cdot 81 \bmod{10000}) \bmod{10000})$$

$$= (2020) + ( 2161 \cdot 5521) \bmod{10000}$$

$$= (2020 + 881) \bmod{10000}$$

$$= \fbox{2901}$$

- 4 years, 7 months ago