2021 WSMO Accuracy Round Problems/Problem 7

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, $$ (Error compiling LaTeX. Unknown error_msg) \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$ (Error compiling LaTeX. Unknown error_msg)n\equiv2\pmod{4}$}\\

2^n+3^n\equiv&\text{ }7\pmod{10}\tag{for$ (Error compiling LaTeX. Unknown error_msg)n\equiv0\pmod{4}$}\\ \end{align*}<cmath> This means that </cmath> \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$ (Error compiling LaTeX. Unknown error_msg)2^i\text{ (mod }10\text{)}3^i\text{ (mod }10\text{)}$:

<cmath>2^1 \equiv 2\text{ (mod }10\text{)}</cmath> <cmath>2^2 \equiv 4\text{ (mod }10\text{)}</cmath> <cmath>2^3 \equiv 8\text{ (mod }10\text{)}</cmath> <cmath>2^4 \equiv 6\text{ (mod }10\text{)}</cmath> <cmath>...</cmath> and <cmath>3^1 \equiv 3\text{ (mod }10\text{)}</cmath> <cmath>3^2 \equiv 9\text{ (mod }10\text{)}</cmath> <cmath>3^3 \equiv 7\text{ (mod }10\text{)}</cmath> <cmath>3^4 \equiv 1\text{ (mod }10\text{)}</cmath> <cmath>...</cmath>

From this, we can note that:

<cmath>r_i = 5 \text{, } i \equiv 1 \text{ (mod }4\text{)}</cmath> <cmath>r_i = 3 \text{, } i \equiv 2 \text{ (mod }4\text{)}</cmath> <cmath>r_i = 5 \text{, } i \equiv 3 \text{ (mod }4\text{)}</cmath> <cmath>r_i = 7 \text{, } i \equiv 0 \text{ (mod }4\text{)}</cmath>

We can simplify our sum as follows:

<cmath>\sum_{n=1}^{100}\left(\sum_{i=1}^{n}r_i\right)</cmath> <cmath>=100r_1 + 99r_2 + 98r_3 + ... + r_{100}</cmath> <cmath>=(100+96+...+4)r_1 + (99+95+...+3)r_2 + (98+94+...+2)r_3 + (97+93+...+1)r_4</cmath>

Note that$ (Error compiling LaTeX. Unknown error_msg)100+96+...+4 = 4(25+24+...+1) = 4(\frac{25 \cdot 26}{2}) = 1300$:

~BigKahuna227