Difference between revisions of "2021 WSMO Accuracy Round Problems/Problem 7"
Line 4: | Line 4: | ||
==Solution 1== | ==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> | 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> | ||
− | + | <cmath>\begin{align*} | |
− | |||
− | |||
− | \begin{align*} | ||
2^1+3^1\equiv2+3\equiv&\text{ }5\pmod{10}\\ | 2^1+3^1\equiv2+3\equiv&\text{ }5\pmod{10}\\ | ||
2^2+3^2\equiv4+9\equiv13\equiv&\text{ }3\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^3+3^3\equiv8+27\equiv35\equiv&\text{ }5\pmod{10}\\ | ||
2^4+3^4\equiv16+81\equiv97\equiv&\text{ }7\pmod{10}\\ | 2^4+3^4\equiv16+81\equiv97\equiv&\text{ }7\pmod{10}\\ | ||
− | \end{align*} | + | \end{align*}</cmath> |
− | |||
Thus, | Thus, | ||
− | + | <math></math>\begin{align*} | |
− | |||
− | |||
− | \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{ }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{ }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>}\\ | 2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for <math>n\equiv0\pmod{4}</math>}\\ | ||
− | \end{align*} | + | \end{align*}<cmath> |
− | |||
This means that | This means that | ||
− | + | </cmath>\begin{align*} | |
− | |||
− | |||
− | \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)\\ | \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)\\ | &=\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)\\ | ||
Line 35: | Line 24: | ||
&=6500+18000+650\\ | &=6500+18000+650\\ | ||
&=\boxed{25150}\\ | &=\boxed{25150}\\ | ||
− | \end{align*} | + | \end{align*}<math></math> |
− | |||
~pinkpig | ~pinkpig | ||
Revision as of 11:20, 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
Thus,
$$ (Error compiling LaTeX. Unknown error_msg)\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*}
\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*}$$ (Error compiling LaTeX. Unknown error_msg) ~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