Difference between revisions of "2021 WSMO Accuracy Round Problems/Problem 7"
Bigkahuna227 (talk | contribs) (Created page with "==Problem 7== Find the value of <math>\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right),</math> where <math>r_i</math> is the remainder when <math>2^i+3^i</math> is divided by 10...") |
|||
Line 2: | Line 2: | ||
Find the value of <math>\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right),</math> where <math>r_i</math> is the remainder when <math>2^i+3^i</math> is divided by 10. | Find the value of <math>\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right),</math> where <math>r_i</math> is the remainder when <math>2^i+3^i</math> is divided by 10. | ||
− | ==Solution== | + | ==Solution 1== |
+ | From Fermat's Little Theorem, we find that <math>a^n\pmod{10}</math> is periodic in cycles of 4. This means that <math>a^n\equiv a^{n+4}\pmod{10}</math> for all <math>a,n.</math> Now, we will compute the first 4 values of <math>2^n+3^n\pmod{10}.</math> | ||
+ | \begin{align*} | ||
+ | 2^1+3^1\equiv2+3\equiv&\text{ }5\pmod{10}\\ | ||
+ | 2^2+3^2\equiv4+9\equiv13\equiv&\text{ }3\pmod{10}\\ | ||
+ | 2^3+3^3\equiv8+27\equiv35\equiv&\text{ }5\pmod{10}\\ | ||
+ | 2^4+3^4\equiv16+81\equiv97\equiv&\text{ }7\pmod{10}\\ | ||
+ | \end{align*} | ||
+ | Thus, | ||
+ | \begin{align*} | ||
+ | 2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for <math>n\equiv1,3\pmod{4}</math>}\\ | ||
+ | 2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for <math>n\equiv2\pmod{4}</math>}\\ | ||
+ | 2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for <math>n\equiv0\pmod{4}</math>}\\ | ||
+ | \end{align*} | ||
+ | This means that | ||
+ | \begin{align*} | ||
+ | \sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right)&=\sum_{n=4a,1\leq a\leq25}(20a)+\sum_{n=4a+1,0\leq a\leq24}(20a+5)+\sum_{n=4a+2,0\leq a\leq24}(20a+8)+\sum_{n=4a+3,0\leq a\leq24}(20a+13)\\ | ||
+ | &=\frac{25\cdot26}{2}\cdot20+\left(\frac{24\cdot25}{2}\cdot20+25\cdot5\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot8\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot13\right)\\ | ||
+ | &=325\cdot20+300\cdot20\cdot3+25\cdot(5+8+13)\\ | ||
+ | &=6500+6000\cdot3+25\cdot26\\ | ||
+ | &=6500+18000+650\\ | ||
+ | &=\boxed{25150}\\ | ||
+ | \end{align*} | ||
+ | ~pinkpig | ||
+ | |||
+ | ==Solution 2== | ||
We will begin by examining <math>2^i\text{ (mod }10\text{)}</math> and <math>3^i\text{ (mod }10\text{)}</math>: | We will begin by examining <math>2^i\text{ (mod }10\text{)}</math> and <math>3^i\text{ (mod }10\text{)}</math>: | ||
Revision as of 11:18, 11 July 2022
Problem 7
Find the value of where
is the remainder when
is divided by 10.
Solution 1
From Fermat's Little Theorem, we find that is periodic in cycles of 4. This means that
for all
Now, we will compute the first 4 values of
\begin{align*}
2^1+3^1\equiv2+3\equiv&\text{ }5\pmod{10}\\
2^2+3^2\equiv4+9\equiv13\equiv&\text{ }3\pmod{10}\\
2^3+3^3\equiv8+27\equiv35\equiv&\text{ }5\pmod{10}\\
2^4+3^4\equiv16+81\equiv97\equiv&\text{ }7\pmod{10}\\
\end{align*}
Thus,
\begin{align*}
2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for }\\
2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for}\\
2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for }\\
\end{align*}
This means that
\begin{align*}
\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right)&=\sum_{n=4a,1\leq a\leq25}(20a)+\sum_{n=4a+1,0\leq a\leq24}(20a+5)+\sum_{n=4a+2,0\leq a\leq24}(20a+8)+\sum_{n=4a+3,0\leq a\leq24}(20a+13)\\
&=\frac{25\cdot26}{2}\cdot20+\left(\frac{24\cdot25}{2}\cdot20+25\cdot5\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot8\right)+\left(\frac{24\cdot25}{2}\cdot20+25\cdot13\right)\\ &=325\cdot20+300\cdot20\cdot3+25\cdot(5+8+13)\\ &=6500+6000\cdot3+25\cdot26\\ &=6500+18000+650\\ &=\boxed{25150}\\
\end{align*} ~pinkpig
Solution 2
We will begin by examining and
:
and
From this, we can note that:
We can simplify our sum as follows:
Note that :
~BigKahuna227