Gargantuan Prime

Let p be the largest prime less than 2013 for which

N=20+ppp+1−13N = 20 + p^{p^{p + 1} - 13}

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

Note by Mharfe Micaroz
8 years ago

No vote yet
2 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Obviously p=2011p=2011

So we want to find

(20+201120112012−13) mod 10000 (20 + 2011^{2011^{2012}-13} ) \bmod{10000}

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

20112012 mod 4000 2011^{2012} \bmod{4000}

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

=1211006 mod 4000 = 121^{1006} \bmod{4000}

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

=2641503 mod 4000 = 2641^{503} \bmod{4000}

=(2641502⋅2641) mod 4000 = ( 2641^{502} \cdot 2641 ) \bmod{4000}

=((26412 mod 4000)251⋅2641) mod 4000 = ( (2641^2 \bmod{4000})^{251} \cdot 2641 ) \bmod{4000}

=(2881251⋅2641) mod 4000 = ( 2881^{251} \cdot 2641 ) \bmod{4000}

=(2881250⋅2641⋅2881) mod 4000 = ( 2881^{250} \cdot 2641 \cdot 2881) \bmod{4000}

=((28812 mod 4000)125⋅2641⋅2881) mod 4000 = ( (2881^2 \bmod{4000})^{125} \cdot 2641 \cdot 2881) \bmod{4000}

=(161125⋅2641⋅2881) mod 4000 = ( 161^{125} \cdot 2641 \cdot 2881) \bmod{4000}

=(161125⋅2641⋅2881) mod 4000 = ( 161^{125} \cdot 2641 \cdot 2881) \bmod{4000}

=(161124⋅2641⋅2881⋅161) mod 4000 = ( 161^{124} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}

=((1612 mod 4000)62⋅2641⋅2881⋅161) mod 4000 = ( (161^2 \bmod{4000})^{62} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}

=(192162⋅2641⋅2881⋅161) mod 4000 = ( 1921^{62} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}

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

=(224131⋅2641⋅2881⋅161) mod 4000 = ( 2241^{31} \cdot 2641 \cdot 2881 \cdot 161) \bmod{4000}

=(224130⋅2641⋅2881⋅161⋅2241) mod 4000 = ( 2241^{30} \cdot 2641 \cdot 2881 \cdot 161 \cdot 2241) \bmod{4000}

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

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

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

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

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

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

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

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

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

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

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

=((3841⋅2641 mod 4000)⋅(2881⋅161 mod 4000)⋅(2241⋅2081 mod 4000)⋅(2561⋅2721 mod 4000)) mod 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⋅3841⋅3521⋅481) mod 4000 = ( 81 \cdot 3841 \cdot 3521 \cdot 481) \bmod{4000}

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

=(3121⋅1601) mod 4000 = (3121 \cdot 1601) \bmod{4000}

=721 = 721

(20112012−13) mod 4000=708 (2011^{2012} - 13 ) \bmod{4000} = 708

So,

(20+201120112012−13) mod 10000 (20 + 2011^{2011^{2012}-13} ) \bmod{10000}

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

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

Notice that by Binomial Theorem

2011708=(2000+11)708=11708+11707⋅2000+10000A2011^{708} = (2000 + 11)^{708} = 11^{708} + 11^{707} \cdot 2000 + 10000A , for some integer AA

⇒2011708 mod 10000=(11708+11707⋅2000) mod 10000 \Rightarrow 2011^{708} \bmod{10000} = (11^{708} + 11^{707} \cdot 2000 ) \bmod 10000

Continue:

=(20+(11708+11707⋅2000)) mod 10000 = (20 + (11^{708} + 11^{707} \cdot 2000 ) ) \bmod{10000}

=(20)+(11708 mod 10000)+(11707⋅2000 mod 10000) = (20) + (11^{708} \bmod 10000) + (11^{707} \cdot 2000 \bmod{10000})

Since 1170711^{707} ends with 11 because 1⋅1⋅…⋅1=11 \cdot 1 \cdot \ldots \cdot 1 = 1, then the last four digits of 11707⋅100011^{707} \cdot 1000 is 10001000, or the last four digits of 11707⋅200011^{707} \cdot 2000 is 20002000 ⇒(11707⋅2000 mod 10000)=2000 \Rightarrow (11^{707} \cdot 2000 \bmod{10000}) = 2000

Continue:

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

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

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

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

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

=(2020)+(4641176⋅4641 mod 10000) = (2020) + ( 4641^{176} \cdot 4641 \bmod{10000})

=(2020)+((46412 mod 10000)88⋅4641 mod 10000 = (2020) + ( (4641^2 \bmod{10000})^{88} \cdot 4641 \bmod{10000}

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

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

=(2020)+(216144⋅4641 mod 10000) = (2020) + ( 2161^{44} \cdot 4641 \bmod{10000})

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

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

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

=(2020)+(624111⋅4641 mod 10000) = (2020) + ( 6241^{11} \cdot 4641 \bmod{10000})

=(2020)+(624110⋅4641⋅6241 mod 10000) = (2020) + ( 6241^{10} \cdot 4641 \cdot 6241 \bmod{10000})

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

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

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

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

=(2020)+(65612⋅4641⋅6241⋅81 mod 10000) = (2020) + ( 6561^2 \cdot 4641 \cdot 6241 \cdot 81 \bmod 10000)

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

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

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

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

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

=2901 = \fbox{2901}

Pi Han Goh - 8 years ago
×

Problem Loading...

Note Loading...

Set Loading...