Let see who is smart

172 9 1728 + 173 1 1730 + 173 3 1732 + + 201 5 2014 + 201 7 2016 \large 1729^{1728}+1731^{1730}+1733^{1732}+\cdots + 2015^{2014}+2017^{2016}

Find the remainder when the expression above is divided by 8.


The answer is 1.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Chew-Seong Cheong
Nov 15, 2017

Relevant wiki: Euler's Theorem

k = 0 144 ( 1729 + 2 k ) 1728 + 2 k k = 0 144 ( 1729 + 2 k ) 1728 + 2 k m o d ϕ ( 8 ) (mod 8) Since gcd ( 1729 + 2 k , 8 ) = 1 , Euler’s theorem applies. k = 0 144 ( 1729 + 2 k ) 1728 + 2 k m o d 4 (mod 8) Euler’s totient function ϕ ( 8 ) = 4 k = 0 144 ( 1729 + 2 k ) { 0 if k is even. 2 if k is odd. (mod 8) ( k = 0 72 ( 1729 + 4 k ) 0 + k = 0 71 ( 1731 + 4 k ) 2 ) (mod 8) ( k = 0 72 1 + k = 0 71 ( 1728 + 3 + 4 k ) 2 ) (mod 8) ( 73 + k = 0 71 ( 3 + 4 k ) 2 ) (mod 8) ( 1 + k = 0 71 ( 9 + 12 k + 16 k 2 ) ) (mod 8) ( 1 + k = 0 71 ( 1 + 4 k ) ) (mod 8) ( 1 + 72 + 4 × 71 ( 72 ) 2 ) (mod 8) ( 1 + 0 + 4 + 0 ) (mod 8) 1 (mod 8) \begin{aligned} \sum_{k=0}^{144} (1729+2k)^{1728+2k} & \equiv \sum_{k=0}^{144} (1729+2k)^{\color{#3D99F6}1728+2k \bmod \phi (8)} \text{ (mod 8)} & \small \color{#3D99F6} \text{Since }\gcd(1729+2k,8) = 1 \text{, Euler's theorem applies.} \\ & \equiv \sum_{k=0}^{144} (1729+2k)^{\color{#3D99F6}1728+2k \bmod 4} \text{ (mod 8)} & \small \color{#3D99F6} \text{Euler's totient function }\phi (8) = 4 \\ & \equiv \sum_{k=0}^{144} (1729+2k)^{\begin{cases} 0 & \text{if }k \text{ is even.} \\ 2 & \text{if }k \text{ is odd.} \end{cases}} \text{ (mod 8)} \\ & \equiv \left(\sum_{k=0}^{72} (1729+4k)^0 + \sum_{k=0}^{71} (1731+4k)^2\right) \text{ (mod 8)} \\ & \equiv \left(\sum_{k=0}^{72} 1 + \sum_{k=0}^{71} (1728+3+4k)^2\right) \text{ (mod 8)} \\ & \equiv \left(73 + \sum_{k=0}^{71} (3+4k)^2\right) \text{ (mod 8)} \\ & \equiv \left(1 + \sum_{k=0}^{71} (9+12k+16k^2)\right) \text{ (mod 8)} \\ & \equiv \left(1 + \sum_{k=0}^{71} (1+4k) \right) \text{ (mod 8)} \\ & \equiv \left(1 + 72 +4 \times \frac {71(72)}2 \right) \text{ (mod 8)} \\ & \equiv \left(1 + 0+4 + 0 \right) \text{ (mod 8)} \\ & \equiv \boxed{1} \text{ (mod 8)} \end{aligned}

Rohith M.Athreya
Nov 14, 2017

Firstly note that odd numbers are raised to even powers which means that each term of the sum is the square of an odd number. Any number of the form ( 2 n + 1 ) 2 = 4 n ( n + 1 ) + 1 (2n+1)^{2}=4n(n+1)+1 is congruent to 1 mod 8. Since there are 145 such terms in the sum, the remainder when it is divided by 8, is the same as when 145 is divided by 8. This,very obviously,is 1.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...