Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question:

let $$a_{n}=1+2^2+3^3+\cdots+n^n$$ find this $$a_{2013}=1^2+2^2+\cdots+2013^{2013} \equiv \; \pmod{10}$$

My try: maybe $a_{n} \pmod{10}$ periodic, but I can't find it. Maybe this problem has nice methods. Thank you for you help!

share|improve this question
    
The terms are periodic; not a period of ten, because of the exponents, but it will be some multiple of ten. –  Dustan Levenstein Dec 6 '13 at 15:04
    
The most obvious starting point is to actually simplify all the numbers modulo $10$. The next most obvious thing to do (once you've seen the trick) is to simplify the exponents. –  Hurkyl Dec 6 '13 at 18:53

3 Answers 3

up vote 7 down vote accepted

When you are looking at numbers (mod 10), you only ever need to consider the final digit. Specifically $$n^n \ (\text{mod } 10) = (n \ (\text{mod } 10))^n \ (\text{mod } 10)$$ For example $12^{12} \ (\text{mod } 10) = 2^{12}\ (\text{mod } 10)$. This holds because the last digit of the product of two integers is the last digit of the product of the last digits of the two integers.

This means that we need to consider only the periodic behaviour of single digits raised to various powers. Here is the periodicity of single digits raised to successive integer powers:

$$ \begin{array}{c|cccccccccc} n & \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 0 & 1 & 4 & 9 & 6 & 5 & 6 & 9 & 4 & 1 \\ 3 & 0 & 1 & 8 & 7 & 4 & 5 & 6 & 3 & 2 & 9 \\ 4 & 0 & 1 & 6 & 1 & 6 & 5 & 6 & 1 & 6 & 1 \\ \end{array} $$

For $n \ge 5$ the table repeats modulo 4.

This gives you the periodicity you're looking for to solve the problem. The base of each term in the original series can be considered modulo 10 and the exponent of each term can be considered modulo 4.

The first 12 terms in the series are therefore: $$ \begin{array}{rcrcl} 1^1 &=& && 1 & (\text{mod } 10) \\ 2^2 &=& && 4 & (\text{mod } 10) \\ 3^3 &=& && 7 & (\text{mod } 10) \\ 4^4 &=& && 6 & (\text{mod } 10) \\ 5^5 &=& 5^1 &=& 5 & (\text{mod } 10) \\ 6^6 &=& 6^2 &=& 6 & (\text{mod } 10) \\ 7^7 &=& 7^3 &=& 3 & (\text{mod } 10) \\ 8^8 &=& 8^4 &=& 6 & (\text{mod } 10) \\ 9^9 &=& 9^1 &=& 9 & (\text{mod } 10) \\ 10^{10} &=& 0^2 &=& 0 & (\text{mod } 10) \\ 11^{11} &=& 1^3 &=& 1 & (\text{mod } 10) \\ 12^{12} &=& 2^4 &=& 6 & (\text{mod } 10) \\ \end{array} $$ How far do we have to go with this table before the numbers on the right keep repeating? Since $$ (n+20)^{n+20} = n^n \text{ (mod 10)} $$ the pattern will start repeating after at most 20 entries in the table. The following completes the table: $$ \begin{array}{rcrcl} 13^{13} &=& 3^1 &=& 3 & (\text{mod } 10) \\ 14^{14} &=& 4^2 &=& 6 & (\text{mod } 10) \\ 15^{15} &=& 5^3 &=& 5 & (\text{mod } 10) \\ 16^{16} &=& 6^4 &=& 6 & (\text{mod } 10) \\ 17^{17} &=& 7^1 &=& 7 & (\text{mod } 10) \\ 18^{18} &=& 8^2 &=& 4 & (\text{mod } 10) \\ 19^{19} &=& 9^3 &=& 9 & (\text{mod } 10) \\ 20^{20} &=& 0^4 &=& 0 & (\text{mod } 10) \\ \end{array} $$ This gives us the sum of any 20 consecutive terms in the series as $$ \begin{array}{l} 1+4+7+6+5+6+3+6+9+0+\\ 1+6+3+6+5+6+7+4+9+0 = 4 \text{ (mod 10)} \end{array} $$ This also means that the sum of any 100 consecutive terms is 0 modulo 10 (since $4 \times 5 = 0 \text{ (mod 10)}$. Therefore $$ \begin{align} & 1^1 + 2^2 + \cdots + 2013^{2013} \\ =& 1^1 + 2^2 + \cdots + 13^{13} \text{ (mod 10)} \\ =& 1+4+7+6+5+6+3+6+9+0+1+6+3 \text{ (mod 10)} \\ =& 7 \text{ (mod 10)} \end{align} $$

share|improve this answer
    
This seems to be an interesting question . I am not much familiar with modulo arithmetic , can you please tell me how did you come with the identity you have written . Thanks in advance ! –  Zoro Dec 6 '13 at 15:33
1  
@TrafalgarLaw The mod identity comes from working in the decimal number system. Whenever you work modulo 10 in the decimal system, the last digit of a product is the last digit of the products of the last digits. This is because $(10a + b)(10c + d) = 100ac + 10(ad+bc) + bd$. If $b$ and $d$ are digits, the only term on the right hand side that affects the last digit of the product is $bd$, the product of the last digits. Following the same reasoning, the last digit of an integer raised to an integer power is the last digit of (the last digit raised to the integer power). –  Carl Dec 9 '13 at 14:30
1  
+1 The observation that the period is $20$ means that the sum of every consecutive $20\cdot10$ values is $0$, regardless of whatever the sum of the first $20$ are. It reduces to $2001^{2001}+\cdots+2013^{2013}$ without a lot of explicit calculation. –  alex.jordan Dec 9 '13 at 15:11
1  
@alex.jordan Even better: it reduces to $1^1 + 2^2 + \cdots + 13^{13}$ since the last $2000$ terms also sum to $0$ modulo $10$. –  Carl Dec 9 '13 at 16:52

The value of $a^b$ modulo 10 (for $a, b >0$) depends on the value of $a$ modulo 10 and the value of $b$ modulo $\phi(10) = 4$. For $n=a=b$ both of these are determined by the the value of $n$ modulo 20, so $(n^n)$ is periodic with period 20.

share|improve this answer
    
I should also point out that the reason this is still true when $\gcd(a,10) \neq 1$ is because $10$ has no repeated prime factors. Otherwise it would only be guaranteed to be true for sufficiently large $b$. –  universalset Dec 6 '13 at 15:15

as $\phi(10) = 4$ then $n^k=n^r (mod 10)$ where $k=r$ mod $(4)$ example : $2=2 (mod 10), 2^2=4 (mod 10), 2^3= 8 (mod 10), 2^4= 6 (mod 10), 2^5= 2 (mod 10)$ $4=4 (mod 10), 4^2=6 (mod 10), 4^3= 4 (mod 10), 4^4= 6 (mod 10)$..

and so on there is always a cycle of 4(not necessarily minimal) for any n that you pick.. now i will rewrite the sum as :

$1 + \sum_{n=1}^{503} (4n-2)^{4n-2} +\sum_{n=1}^{503} (4n-1)^{4n-1}+\sum_{n=1}^{503} (4n)^{4n}+\sum_{n=1}^{503} (4n+1)^{4n+1}$.

observe that: \begin{align} (\sum_{n=1}^{503} (4n-2)^{4n-2}) (mod 10)=(\sum_{n=1}^{503} (4n-2)^{4n-2} (mod 10))=(\sum_{n=1}^{503} (4n-2)^{2} (mod 10)) \end{align}\begin{align} (\sum_{n=1}^{503} (4n-1)^{4n-1}) (mod 10)=(\sum_{n=1}^{503} (4n-1)^{4n-1} (mod 10))=(\sum_{n=1}^{503} ((4n-1)^{3}(mod 10))\end{align}\begin{align} (\sum_{n=1}^{503} (4n)^{4n}) (mod 10)=(\sum_{n=1}^{503} (4n)^{4n} (mod 10))=(\sum_{n=1}^{503} (4n)^{4} (mod 10))\end{align}\begin{align} (\sum_{n=1}^{503} (4n+1)^{4n+1}) (mod 10)=(\sum_{n=1}^{503} (4n+1)^{4n+1} (mod 10))=(\sum_{n=1}^{503} (4n+1) (mod 10)) \end{align} the proof of some of the above work is left to the reader. observe now that $n (mod 10) =(n+10) mod (10)$ therefore: all the sums will be reduced to: \begin{align} (\sum_{n=1}^{503} (4n-2)^{2} (mod 10))=(\sum_{n=501}^{503} (4n-2)^{2} (mod 10))=(\sum_{n=1}^{3} (4n-2)^{2} (mod 10))= 0 mod(10)\end{align}\begin{align} (\sum_{n=1}^{503} ((4n-1)^{3}(mod 10))=(\sum_{n=501}^{503} ((4n-1)^{3}(mod 10))=(\sum_{n=1}^{3} ((4n-1)^{3}(mod 10))= 1 mod(10)\end{align}\begin{align} (\sum_{n=1}^{503} (4n+1) (mod 10))=(\sum_{n=501}^{503} (4n+1) (mod 10))=(\sum_{n=1}^{3} (4n+1) (mod 10))= 7mod(10)\end{align}\begin{align} (\sum_{n=1}^{503} (4n)^{4} (mod 10))=(\sum_{n=501}^{503} (4n)^{4} (mod 10))=(\sum_{n=1}^{3} (4n)^{4} (mod 10))=8mod(10)\end{align} consequently : $1 + 2^2 + \cdots + 2013^{2013} \equiv \; (1+0+1+7+8) \pmod{10}\equiv \; 7 \pmod{10}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.