https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&feed=atom&action=history
2021 AIME I Problems/Problem 14 - Revision history
2024-03-29T10:19:09Z
Revision history for this page on the wiki
MediaWiki 1.31.1
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=202912&oldid=prev
Ryanjwang: /* Remark (Dirichlet's Theorem) */
2023-11-13T06:28:13Z
<p><span dir="auto"><span class="autocomment">Remark (Dirichlet's Theorem)</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 06:28, 13 November 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l113" >Line 113:</td>
<td colspan="2" class="diff-lineno">Line 113:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Remark (Dirichlet's Theorem)==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Remark (Dirichlet's Theorem)==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>All solutions require Dirichlet's Theorem, which states that for any coprime integers <math>k</math> and <math>r</math>, there <del class="diffchange diffchange-inline">is a prime </del><math>p</math> congruent to <math>r\pmod{k}</math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>All solutions require Dirichlet's Theorem, which states that for any coprime <ins class="diffchange diffchange-inline">positive </ins>integers <math>k</math> and <math>r</math>, there <ins class="diffchange diffchange-inline">are infinitely many primes </ins><math>p</math> congruent to <math>r\pmod{k}</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Video Solution==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Video Solution==</div></td></tr>
</table>
Ryanjwang
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=200173&oldid=prev
Happypi31415: /* Solution 1 */
2023-10-25T19:07:52Z
<p><span dir="auto"><span class="autocomment">Solution 1</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 19:07, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l11" >Line 11:</td>
<td colspan="2" class="diff-lineno">Line 11:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Alternatively, since <math>\left(\frac{a(a^n - 1^n)}{a-1}\right)</math> must be divisible by <math>43,</math> by LTE, we have <math>v_{43}<del class="diffchange diffchange-inline">{</del>a<del class="diffchange diffchange-inline">}</del>+v_{43}{(a-1)}+v_{43}{n}-v_{43}{(a-1)} \geq 1,</math> which simplifies to <math>v_{43}n \geq 1,</math> which implies the desired result.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Alternatively, since <math>\left(\frac{a(a^n - 1^n)}{a-1}\right)</math> must be divisible by <math>43,</math> by LTE, we have <math>v_{43}<ins class="diffchange diffchange-inline">(</ins>a<ins class="diffchange diffchange-inline">)</ins>+v_{43}{(a-1)}+v_{43}{<ins class="diffchange diffchange-inline">(</ins>n<ins class="diffchange diffchange-inline">)</ins>}-v_{43}{(a-1)} \geq 1,</math> which simplifies to <math>v_{43}<ins class="diffchange diffchange-inline">(</ins>n<ins class="diffchange diffchange-inline">) </ins>\geq 1,</math> which implies the desired result.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similarly, <math>n</math> is a multiple of <math>47</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similarly, <math>n</math> is a multiple of <math>47</math>.</div></td></tr>
</table>
Happypi31415
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=200172&oldid=prev
Happypi31415: /* Solution 1 */
2023-10-25T19:07:04Z
<p><span dir="auto"><span class="autocomment">Solution 1</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 19:07, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l11" >Line 11:</td>
<td colspan="2" class="diff-lineno">Line 11:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Alternatively, since <math>\left(\frac{a(a^n - 1^n)}{a-1}\right)</math> must be divisible by <math>43,</math> by LTE, we have <math>v_{43}{a}+v_{43}{a-1}+v_{43}{n}-v_{43}{<del class="diffchange diffchange-inline">p</del>-1} \geq 1,</math> which simplifies to <math>v_{43}n \geq 1,</math> which implies the desired result.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Alternatively, since <math>\left(\frac{a(a^n - 1^n)}{a-1}\right)</math> must be divisible by <math>43,</math> by LTE, we have <math>v_{43}{a}+v_{43}{<ins class="diffchange diffchange-inline">(</ins>a-1<ins class="diffchange diffchange-inline">)</ins>}+v_{43}{n}-v_{43}{<ins class="diffchange diffchange-inline">(a</ins>-1<ins class="diffchange diffchange-inline">)</ins>} \geq 1,</math> which simplifies to <math>v_{43}n \geq 1,</math> which implies the desired result.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similarly, <math>n</math> is a multiple of <math>47</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similarly, <math>n</math> is a multiple of <math>47</math>.</div></td></tr>
</table>
Happypi31415
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=200171&oldid=prev
Happypi31415: /* Solution 1 */
2023-10-25T19:05:26Z
<p><span dir="auto"><span class="autocomment">Solution 1</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 19:05, 25 October 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l10" >Line 10:</td>
<td colspan="2" class="diff-lineno">Line 10:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math>. By Dirichlet, let <math>a</math> be a prime that is congruent to <math>1 \pmod{43}</math>. Then <math>\sigma(a^n) \equiv n+1 \pmod{43}</math>, so since <math>\sigma(a^n)-1</math> is divisible by <math>43</math>, <math>n</math> is a multiple of <math>43</math>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Alternatively, since <math>\left(\frac{a(a^n - 1^n)}{a-1}\right)</math> must be divisible by <math>43,</math> by LTE, we have <math>v_{43}{a}+v_{43}{a-1}+v_{43}{n}-v_{43}{p-1} \geq 1,</math> which simplifies to <math>v_{43}n \geq 1,</math> which implies the desired result.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similarly, <math>n</math> is a multiple of <math>47</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similarly, <math>n</math> is a multiple of <math>47</math>.</div></td></tr>
</table>
Happypi31415
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=183513&oldid=prev
MRENTHUSIASM: /* Solution 1 */
2022-12-04T09:05:59Z
<p><span dir="auto"><span class="autocomment">Solution 1</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 09:05, 4 December 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3" >Line 3:</td>
<td colspan="2" class="diff-lineno">Line 3:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <math>a</math> is prime and <math>a \neq 0,1 \pmod{43}</math>. By Dirichlet's Theorem (Refer to the <b>Remark</b> <del class="diffchange diffchange-inline">Section</del>.), such <math>a</math> always exists.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <math>a</math> is prime and <math>a \neq 0,1 \pmod{43}</math>. By Dirichlet's Theorem (Refer to the <b>Remark</b> <ins class="diffchange diffchange-inline">section</ins>.), such <math>a</math> always exists.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>.</div></td></tr>
</table>
MRENTHUSIASM
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=183512&oldid=prev
MRENTHUSIASM: /* Solution 1 */
2022-12-04T09:05:22Z
<p><span dir="auto"><span class="autocomment">Solution 1</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 09:05, 4 December 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3" >Line 3:</td>
<td colspan="2" class="diff-lineno">Line 3:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <math>a</math> is prime and <math>a \neq 0,1 \pmod{43}</math>. By Dirichlet's Theorem, such <math>a</math> always exists.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <math>a</math> is prime and <math>a \neq 0,1 \pmod{43}</math>. By Dirichlet's Theorem <ins class="diffchange diffchange-inline">(Refer to the <b>Remark</b> Section.)</ins>, such <math>a</math> always exists.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>.</div></td></tr>
</table>
MRENTHUSIASM
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=183419&oldid=prev
MRENTHUSIASM: /* Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4) */
2022-12-02T20:00:22Z
<p><span dir="auto"><span class="autocomment">Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)</span></span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 20:00, 2 December 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l109" >Line 109:</td>
<td colspan="2" class="diff-lineno">Line 109:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It says the problem implies that it works for all positive integers <math>a</math>, we basically know that If <math>p \equiv 1 \pmod q</math>, then from "USEMO 2019 Problem 4", if <math>p^n + p^{n-1} + \cdots + 1 \equiv 1 \pmod{q}</math>, then <cmath>\frac{p^{en+1}-1}{p-1} = p^{en} + p^{en-1} + \cdots + 1 \equiv 1 \pmod{q}.</cmath> From here we can just let <math>\sigma(2^n)</math> or be a power of <math>2</math> which we can do <cmath>\sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1,</cmath> which is a geometric series. We can plug in <math>a=2</math> like in Solution 4 and use CRT. We have the prime factorization <math>2021 = 43 \cdot 47</math>. We use CRT to find that <cmath>\begin{align*} 2^n &\equiv 1 \pmod{43}, \\ 2^n &\equiv 1 \pmod{47}. \end{align*}</cmath> We see that this is just FLT which is <math>a^{p-1} \equiv 1 \pmod p</math> we see that all multiples of <math>42</math> will work for first and <math>46</math> for the second. We can figure out that it is just <math>\text{lcm}(43-1,47-1)\cdot43\cdot47</math> which when we add up we get that it's just the sum of the prime factors of <math>\text{lcm}(42,43,46,47)</math> which you can just look at Solution 1 to find out the sum of the prime factors and get the answer <math>\boxed{125}</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>It says the problem implies that it works for all positive integers <math>a</math>, we basically know that If <math>p \equiv 1 \pmod q</math>, then from "USEMO 2019 Problem 4", if <math>p^n + p^{n-1} + \cdots + 1 \equiv 1 \pmod{q}</math>, then <cmath>\frac{p^{en+1}-1}{p-1} = p^{en} + p^{en-1} + \cdots + 1 \equiv 1 \pmod{q}.</cmath> From here we can just let <math>\sigma(2^n)</math> or be a power of <math>2</math> which we can do <cmath>\sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1,</cmath> which is a geometric series. We can plug in <math>a=2</math> like in Solution 4 and use CRT. We have the prime factorization <math>2021 = 43 \cdot 47</math>. We use CRT to find that <cmath>\begin{align*} 2^n &\equiv 1 \pmod{43}, \\ 2^n &\equiv 1 \pmod{47}. \end{align*}</cmath> We see that this is just FLT which is <math>a^{p-1} \equiv 1 \pmod p</math> we see that all multiples of <math>42</math> will work for first and <math>46</math> for the second. We can figure out that it is just <math>\text{lcm}(43-1,47-1)\cdot43\cdot47</math> which when we add up we get that it's just the sum of the prime factors of <math>\text{lcm}(42,43,46,47)</math> which you can just look at Solution 1 to find out the sum of the prime factors and get the answer <math>\boxed{125}</math>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Remark (Dirichlet's Theorem)==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">All solutions require Dirichlet's Theorem, which states that for any coprime integers <math>k</math> and <math>r</math>, there is a prime <math>p</math> congruent to <math>r\pmod{k}</math>.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Video Solution==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Video Solution==</div></td></tr>
</table>
MRENTHUSIASM
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=183418&oldid=prev
MRENTHUSIASM: /* Dirichlet's Theorem */ Will move this to REMARK.
2022-12-02T19:59:45Z
<p><span dir="auto"><span class="autocomment">Dirichlet's Theorem: </span> Will move this to REMARK.</span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 19:59, 2 December 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Problem==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Problem==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>For any positive integer <math>a, \sigma(a)</math> denotes the sum of the positive integer divisors of <math>a</math>. Let <math>n</math> be the least positive integer such that <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>. Find the sum of the prime factors in the prime factorization of <math>n</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>For any positive integer <math>a, \sigma(a)</math> denotes the sum of the positive integer divisors of <math>a</math>. Let <math>n</math> be the least positive integer such that <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>. Find the sum of the prime factors in the prime factorization of <math>n</math>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">==Dirichlet's Theorem==</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">All solutions require Dirichlet's Theorem, which states that for any coprime integers <math>k</math> and <math>r</math>, there is a prime <math>p</math> congruent to <math>r\pmod{k}</math>.</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td></tr>
</table>
MRENTHUSIASM
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=183398&oldid=prev
Wzs26843545602: This solution is wrong on so many details I can't believe no one pointed it out
2022-12-02T14:26:16Z
<p>This solution is wrong on so many details I can't believe no one pointed it out</p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 14:26, 2 December 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Problem==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Problem==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>For any positive integer <math>a, \sigma(a)</math> denotes the sum of the positive integer divisors of <math>a</math>. Let <math>n</math> be the least positive integer such that <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>. Find the sum of the prime factors in the prime factorization of <math>n</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>For any positive integer <math>a, \sigma(a)</math> denotes the sum of the positive integer divisors of <math>a</math>. Let <math>n</math> be the least positive integer such that <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>. Find the sum of the prime factors in the prime factorization of <math>n</math>.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">==Dirichlet's Theorem==</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">All solutions require Dirichlet's Theorem, which states that for any coprime integers <math>k</math> and <math>r</math>, there is a prime <math>p</math> congruent to <math>r\pmod{k}</math>.</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 1==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <math>a \neq 0,1 \pmod{43}</math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We first claim that <math>n</math> must be divisible by <math>42</math>. Since <math>\sigma(a^n)-1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>, we can first consider the special case where <ins class="diffchange diffchange-inline"><math>a</math> is prime and </ins><math>a \neq 0,1 \pmod{43}</math><ins class="diffchange diffchange-inline">. By Dirichlet's Theorem, such <math>a</math> always exists</ins>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then <math>\sigma(a^n)-1 = \sum_{i=1}^n a^i = a\left(\frac{a^n - 1}{a-1}\right)</math>. In order for this expression to be divisible by <math>2021=43\cdot 47</math>, a necessary condition is <math>a^n - 1 \equiv 0 \pmod{43}</math>. By [[Fermat's Little Theorem]], <math>a^{42} \equiv 1 \pmod{43}</math>. Moreover, if <math>a</math> is a primitive root modulo <math>43</math>, then <math>\text{ord}_{43}(a) = 42</math>, so <math>n</math> must be divisible by <math>42</math>.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l9" >Line 9:</td>
<td colspan="2" class="diff-lineno">Line 12:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>By similar reasoning, <math>n</math> must be divisible by <math>46</math>, by considering <math>a \not\equiv 0,1 \pmod{47}</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>By similar reasoning, <math>n</math> must be divisible by <math>46</math>, by considering <math>a \not\equiv 0,1 \pmod{47}</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math> <del class="diffchange diffchange-inline">and </del><math><del class="diffchange diffchange-inline">47</del></math><del class="diffchange diffchange-inline">. Consider the case </del><math><del class="diffchange diffchange-inline">a=2022</del></math>. Then <math>\sigma(a^n) \equiv n \pmod{<del class="diffchange diffchange-inline">2021</del>}</math>, so <math>\sigma(<del class="diffchange diffchange-inline">2022</del>^n)-1</math> is divisible by <math><del class="diffchange diffchange-inline">2021</del></math> <del class="diffchange diffchange-inline">if and only if </del><math>n</math> is <del class="diffchange diffchange-inline">divisible by </del><math><del class="diffchange diffchange-inline">2021</del></math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>We next claim that <math>n</math> must be divisible by <math>43</math><ins class="diffchange diffchange-inline">. By Dirichlet, let </ins><math><ins class="diffchange diffchange-inline">a</ins></math> <ins class="diffchange diffchange-inline">be a prime that is congruent to </ins><math><ins class="diffchange diffchange-inline">1 \pmod{43}</ins></math>. Then <math>\sigma(a^n) \equiv n<ins class="diffchange diffchange-inline">+1 </ins>\pmod{<ins class="diffchange diffchange-inline">43</ins>}</math>, so <ins class="diffchange diffchange-inline">since </ins><math>\sigma(<ins class="diffchange diffchange-inline">a</ins>^n)-1</math> is divisible by <math><ins class="diffchange diffchange-inline">43</ins></math><ins class="diffchange diffchange-inline">, </ins><math>n</math> is <ins class="diffchange diffchange-inline">a multiple of <math>43</math>.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Similarly, <math>n</math> is a multiple of </ins><math><ins class="diffchange diffchange-inline">47</ins></math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lastly, we claim that if <math>n = \text{lcm}(42, 46, 43, 47)</math>, then <math>\sigma(a^n) - 1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>. The claim is trivially true for <math>a=1</math> so suppose <math>a>1</math>. Let <math>a = p_1^{e_1}\ldots p_k^{e_k}</math> be the prime factorization of <math>a</math>. Since <math>\sigma(n)</math> is [[multiplicative function|multiplicative]], we have</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Lastly, we claim that if <math>n = \text{lcm}(42, 46, 43, 47)</math>, then <math>\sigma(a^n) - 1</math> is divisible by <math>2021</math> for all positive integers <math>a</math>. The claim is trivially true for <math>a=1</math> so suppose <math>a>1</math>. Let <math>a = p_1^{e_1}\ldots p_k^{e_k}</math> be the prime factorization of <math>a</math>. Since <math>\sigma(n)</math> is [[multiplicative function|multiplicative]], we have</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l19" >Line 19:</td>
<td colspan="2" class="diff-lineno">Line 24:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then the prime factors of <math>n</math> are <math>2,3,7,23,43,</math> and <math>47,</math> and the answer is <math>2+3+7+23+43+47 = \boxed{125}</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Then the prime factors of <math>n</math> are <math>2,3,7,23,43,</math> and <math>47,</math> and the answer is <math>2+3+7+23+43+47 = \boxed{125}</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>~scrabbler94</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>~scrabbler94<ins class="diffchange diffchange-inline">, Revised by wzs26843545602</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 2 (Along the Lines of Solution 1)==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 2 (Along the Lines of Solution 1)==</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l99" >Line 99:</td>
<td colspan="2" class="diff-lineno">Line 104:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 4 (Cheap)==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 4 (Cheap)==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Since the problem works for all positive integers <math>a</math>, let's plug in <math>a=2</math> and see what we get. Since <math>\sigma({2^n}) = 2^{n+1}-1,</math> we have <math>2^{n+1} \equiv 2 \pmod{2021}.</math> Simplifying using CRT and [[Fermat's Little Theorem]], we get that <math><del class="diffchange diffchange-inline">2^</del>n \equiv 0 \pmod{42}</math> and <math><del class="diffchange diffchange-inline">2^</del>n \equiv 0 \pmod{46}.</math> Then, we can look at <math>a<del class="diffchange diffchange-inline">=2022</del></math> just like in Solution 1 to find that <math>43</math> and <math>47</math> also divide <math>n</math>. There don't seem to be any other odd "numbers" to check, so we can hopefully assume that the answer is the sum of the prime factors of <math>\text{lcm(42, 43, 46, 47)}.</math> From here, follow solution 1 to get the final answer <math>\boxed{125}</math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Since the problem works for all positive integers <math>a</math>, let's plug in <math>a=2</math> and see what we get. Since <math>\sigma({2^n}) = 2^{n+1}-1,</math> we have <math>2^{n+1} \equiv 2 \pmod{2021}.</math> Simplifying using CRT and [[Fermat's Little Theorem]], we get that <math>n \equiv 0 \pmod{42}</math> and <math>n \equiv 0 \pmod{46}.</math> Then, we can look at <math>a</math> <ins class="diffchange diffchange-inline">being a <math>1\pmod{43}</math> prime and a <math>1\pmod{47}</math> prime, </ins>just like in Solution 1<ins class="diffchange diffchange-inline">, </ins>to find that <math>43</math> and <math>47</math> also divide <math>n</math>. There don't seem to be any other odd "numbers" to check, so we can hopefully assume that the answer is the sum of the prime factors of <math>\text{lcm(42, 43, 46, 47)}.</math> From here, follow solution 1 to get the final answer <math>\boxed{125}</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">-</del>PureSwag</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">~</ins>PureSwag</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 5 (Similar to Solution 4 and USEMO 2019 Problem 4)==</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>It says the problem implies that it works for all positive integers <math>a</math>, we basically know that If <math>p \equiv 1 \pmod q</math>, then from "USEMO 2019 Problem 4", if <math>p^n + p^{n-1} + \cdots + 1 \equiv 1 \pmod{q}</math>, then <cmath>\frac{p^{en+1}-1}{p-1} = p^{en} + p^{en-1} + \cdots + 1 \equiv 1 \pmod{q}.</cmath> From here we can just let <math>\sigma(2^n)</math> or be a power of <math>2</math> which we can do <cmath>\sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1,</cmath> which is a geometric series. We can plug in <math>a=2<del class="diffchange diffchange-inline">^a</del></math> like in Solution 4 and use CRT. We have the prime factorization <math>2021 = 43 \cdot 47</math>. We use CRT to find that <cmath>\begin{align*} 2^n &\equiv 1 \pmod{43}, \\ 2^n &\equiv 1 \pmod{47}. \end{align*}</cmath> We see that this is just FLT which is <math>a^{p-1} \equiv 1 \pmod p</math> we see that all multiples of <math>42</math> will work for first and <math>46</math> for the second. We can figure out that it is just <math>\text{lcm}(43-1,47-1)\cdot43\cdot47</math> which when we add up we get that it's just the sum of the prime factors of <math>\text{lcm}(42,43,46,47)</math> which you can just look at Solution 1 to find out the sum of the prime factors and get the answer <math>\boxed{125}</math>.</div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Warning: This solution doesn't explain why <math>43*47\mid n</math>.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>It says the problem implies that it works for all positive integers <math>a</math>, we basically know that If <math>p \equiv 1 \pmod q</math>, then from "USEMO 2019 Problem 4", if <math>p^n + p^{n-1} + \cdots + 1 \equiv 1 \pmod{q}</math>, then <cmath>\frac{p^{en+1}-1}{p-1} = p^{en} + p^{en-1} + \cdots + 1 \equiv 1 \pmod{q}.</cmath> From here we can just let <math>\sigma(2^n)</math> or be a power of <math>2</math> which we can do <cmath>\sigma(2^n)=1+2+2^2+2^3+2^4+\cdots+2^n=2^{n+1}-1,</cmath> which is a geometric series. We can plug in <math>a=2</math> like in Solution 4 and use CRT. We have the prime factorization <math>2021 = 43 \cdot 47</math>. We use CRT to find that <cmath>\begin{align*} 2^n &\equiv 1 \pmod{43}, \\ 2^n &\equiv 1 \pmod{47}. \end{align*}</cmath> We see that this is just FLT which is <math>a^{p-1} \equiv 1 \pmod p</math> we see that all multiples of <math>42</math> will work for first and <math>46</math> for the second. We can figure out that it is just <math>\text{lcm}(43-1,47-1)\cdot43\cdot47</math> which when we add up we get that it's just the sum of the prime factors of <math>\text{lcm}(42,43,46,47)</math> which you can just look at Solution 1 to find out the sum of the prime factors and get the answer <math>\boxed{125}</math>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Video Solution==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Video Solution==</div></td></tr>
</table>
Wzs26843545602
https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_I_Problems/Problem_14&diff=176882&oldid=prev
MRENTHUSIASM: /* Solution 2 (Along the Lines of Solution 1) */ Removed contributor with minimal credit. Hope I am not making anyone unhappy ...
2022-08-13T08:42:38Z
<p><span dir="auto"><span class="autocomment">Solution 2 (Along the Lines of Solution 1): </span> Removed contributor with minimal credit. Hope I am not making anyone unhappy ...</span></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #222; text-align: center;">Revision as of 08:42, 13 August 2022</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l33" >Line 33:</td>
<td colspan="2" class="diff-lineno">Line 33:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   <li>For all <math>p\equiv1\pmod{43}</math>, it is true that <cmath>p+p^2+\cdots+p^n \equiv n \equiv 0 \pmod{43}.</cmath> One can either use brute force or Dirichlet's Theorem to show such <math>p</math> exists. Therefore, <math>43|n</math>.</li><p></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   <li>For all <math>p\equiv1\pmod{43}</math>, it is true that <cmath>p+p^2+\cdots+p^n \equiv n \equiv 0 \pmod{43}.</cmath> One can either use brute force or Dirichlet's Theorem to show such <math>p</math> exists. Therefore, <math>43|n</math>.</li><p></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   <li>For all <math>p\not\equiv0,1\pmod{43}</math>, it is true that</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>   <li>For all <math>p\not\equiv0,1\pmod{43}</math>, it is true that</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><cmath>p+p^2+\cdots+p^n \equiv 0 \pmod{43} \Leftrightarrow p^n-1\equiv0\pmod{43}.</cmath> According to Fermat's Little Theorem, <math>42|n</math> is sufficient. To show it's necessary, we just need to show <math>43</math> has a prime primitive root. This can be done either by brute force or as follows. <math>43</math> is prime and it must have a primitive root <math>t\neq 1</math> that's coprime to <math>43</math>. All numbers of the form <math>43k+t</math> are also primitive roots of <math>43</math>. According to Dirichlet's Theorem there must be <del class="diffchange diffchange-inline">(</del>infinitely many<del class="diffchange diffchange-inline">) </del>primes among them.</li><p></div></td><td class='diff-marker'>+</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><cmath>p+p^2+\cdots+p^n \equiv 0 \pmod{43} \Leftrightarrow p^n-1\equiv0\pmod{43}.</cmath> According to Fermat's Little Theorem, <math>42|n</math> is sufficient. To show it's necessary, we just need to show <math>43</math> has a prime primitive root. This can be done either by brute force or as follows. <math>43</math> is prime and it must have a primitive root <math>t\neq 1</math> that's coprime to <math>43</math>. All numbers of the form <math>43k+t</math> are also primitive roots of <math>43</math>. According to Dirichlet's Theorem there must be infinitely many primes among them.</li><p></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></ol></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div></ol></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similar arguments for modulo <math>47</math> lead to <math>46|n</math> and <math>47|n</math>. Therefore, we get <math>n=\operatorname{lcm}[42,43,46,47]</math>. Following the last paragraph of Solution 1 gives the answer <math>\boxed{125}</math>.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Similar arguments for modulo <math>47</math> lead to <math>46|n</math> and <math>47|n</math>. Therefore, we get <math>n=\operatorname{lcm}[42,43,46,47]</math>. Following the last paragraph of Solution 1 gives the answer <math>\boxed{125}</math>.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l40" >Line 40:</td>
<td colspan="2" class="diff-lineno">Line 40:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>~MRENTHUSIASM (Reformatting)</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>~MRENTHUSIASM (Reformatting)</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">~lpieleanu (Minor editing)</del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 3 (Casework)==</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #222; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>==Solution 3 (Casework)==</div></td></tr>
</table>
MRENTHUSIASM