×

# 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
3 years, 9 months ago

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}$$ · 3 years, 9 months ago

×