Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
2 votes

Comments

Sort by:

Top Newest

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} \) Pi Han Goh · 3 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...