Difference between revisions of "2021 WSMO Accuracy Round Problems/Problem 7"
(2 intermediate revisions by the same user not shown) | |||
Line 10: | Line 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*}</cmath> | + | \end{align*} </cmath> |
Thus, | Thus, | ||
− | < | + | <cmath> |
\begin{align*} | \begin{align*} | ||
− | 2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for | + | 2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for n\equiv1,3\pmod{4}}\\ |
− | 2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for | + | 2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for n\equiv2\pmod{4}}\\ |
− | 2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for | + | 2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for n\equiv0\pmod{4}}\\ |
− | \end{align*}<cmath> | + | \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)\\ | ||
Line 27: | Line 27: | ||
&=6500+18000+650\\ | &=6500+18000+650\\ | ||
&=\boxed{25150}\\ | &=\boxed{25150}\\ | ||
− | \end{align*}</ | + | \end{align*}</cmath> |
~pinkpig | ~pinkpig | ||
==Solution 2== | ==Solution 2== | ||
− | We will begin by examining < | + | We will begin by examining <math>2^i\text{ (mod }10\text{)}</math> and <math>3^i\text{ (mod }10\text{)}</math>: |
<cmath>2^1 \equiv 2\text{ (mod }10\text{)}</cmath> | <cmath>2^1 \equiv 2\text{ (mod }10\text{)}</cmath> | ||
Line 59: | Line 59: | ||
− | Note that < | + | Note that <math>100+96+...+4 = 4(25+24+...+1) = 4(\frac{25 \cdot 26}{2}) = 1300</math>: |
<cmath>=1300r_1 + (1300-25)r_2 + (1300-50)r_3 + (1300-75)r_4</cmath> | <cmath>=1300r_1 + (1300-25)r_2 + (1300-50)r_3 + (1300-75)r_4</cmath> |
Latest revision as of 11:24, 11 July 2022
Problem
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,
\begin{align*} 2^n+3^n\equiv&\text{ }5\pmod{10}\tag{for n\equiv1,3\pmod{4}}\\ 2^n+3^n\equiv&\text{ }3\pmod{10}\tag{for n\equiv2\pmod{4}}\\ 2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for n\equiv0\pmod{4}}\\ \end{align*} (Error compiling LaTeX. Unknown error_msg)
This means that
~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