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> | ||
+ | \documentclass{article} | ||
+ | \usepackage{amsmath} | ||
+ | \begin{document} | ||
\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}\\ | ||
Line 10: | Line 13: | ||
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*} | ||
+ | \end{document} | ||
Thus, | Thus, | ||
+ | \documentclass{article} | ||
+ | \usepackage{amsmath} | ||
+ | \begin{document} | ||
\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>}\\ | ||
Line 16: | Line 23: | ||
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*} | ||
+ | \end{document} | ||
This means that | This means that | ||
+ | \documentclass{article} | ||
+ | \usepackage{amsmath} | ||
+ | \begin{document} | ||
\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)\\ | ||
Line 25: | Line 36: | ||
&=\boxed{25150}\\ | &=\boxed{25150}\\ | ||
\end{align*} | \end{align*} | ||
+ | \end{document} | ||
~pinkpig | ~pinkpig | ||
Revision as of 11:19, 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
\documentclass{article}
\usepackage{amsmath}
\begin{document}
\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*}
\end{document}
Thus,
\documentclass{article}
\usepackage{amsmath}
\begin{document}
\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*}
\end{document}
This means that
\documentclass{article}
\usepackage{amsmath}
\begin{document}
\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*} \end{document} ~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