Question

challenge question find
\(\sum _{i=1}^{(40)}i^7 \mod 100 \)
i wont be here for at least 4 hours so have fun :P

Answer 1

0 ?

Answer 2

not really a challenge :P

Answer 3

haha m but why zero :P

Answer 4

i was gonna say 99 instead of 7
but though giving the chance for ppl how likes to solve it without back ground

Answer 5

can we say \[\begin{array}{}
\sum\limits_{i=1}^{\phi(a)} i^n \equiv 0 \pmod a &:& \phi(a) \not |~ n \\~\\
\sum\limits_{i=1}^{\phi(a)} i^n \equiv -1 \pmod a &:& \phi(a) | n \\~\\

\end{array} \]

Answer 6

ermm na
see for n>101 this does not work :3

Answer 7

Did someone call me ?

Answer 8

:O speaks of the devil !

Answer 9

Well ?

Answer 10

it should work for all powers
let me check

Answer 11

ok k tbh n>99 does not work

Answer 12

why ?

Answer 13

:D
can u read its a challenge

Answer 14

it works for all powers when the moduli is prime, right ?

Answer 15

:P
yes when the prime <100 and works for other integers
however with phi its not true u need to find some other easy way

Answer 16

100 is not prime , i was about to apply the the conclusion from last question lol

Answer 17

k have to go , have fun !

Answer 18

ok you too have fun :)

Answer 19

playing with snow :3

Answer 20

yeah 100 is not a prime but we can still use the previous result by considering \(\phi (100)\)

Answer 21

@Marki do you have a proof or something for why it doesn't work for composite numbers ?

Answer 22

Oh I see.
composite integers need not have a primitive root and the previous proof breaks

Answer 23

:D

Answer 24

i still dont get why after 4 they are divisible by 100

Answer 25

@ganeshie8 try lol

Answer 26

oh wait i think its faulty lol

Answer 27

is their a partial sum formula to that series

Answer 28

i dnt know all formulas that solves it but u can try why not

Answer 29

Here's one way of doing it that is no doubt inferior to what ganeshie and markie have in mind... But it's fun so I'll start you all out: \[\Large \sum_{i=1}^{40}i^8-(i-1)^8=40^8 \] Take the telescoping series a power above, then expand the binomial **scribbles half of pascal's triangle** \[\sum_{i=1}^{40}i^8-(i^8-8i^7+28i^6-56i^5+70i^4-56i^3+28i^2-8i+1)=40^8\] change some junk around \[\sum_{i=1}^{40}8i^7-28i^6+56i^5-70i^4+56i^3-28i^2+8i-1 =40^8\] \[\sum_{i=1}^{40}i^7 =\frac{1}{8}40^8 + \frac{1}{8}\sum_{i=1}^{40}28i^6-56i^5+70i^4-56i^3+28i^2-8i+1\]

Yay we decreased the order of the sum by 1, let's just repeat this a few more times...

Answer 30

i think it works if we run the sum over numbers that are relatively prime to 100

Answer 31

hahaha what is with u and telescoping series now

Answer 32

@ganeshie8
https://www.wolframalpha.com/input/?i=%5Csum+_%7Bi%3D1%7D%5E%7B40%7Di%5E%7B49%7D+%28mod+100%29+++

Answer 33

Kai's method works always no matter what ! evaluate the sum and find the remainder. pretty straightforward :)

Answer 34

haha yeah indeed

Answer 35

that's why i chose 7 not 99 :P

Answer 36

@Marki I see the remainder of the sum cannot be 0 or -1 for all powers because fermat's little thm requires the base to be relatively prime to the moduli and there will be many integers between 1 and 40 that are not relatively prime to 100

Answer 37

0 for all odd powers of 7 and =/=0 for all even powers of 7?

Answer 38

ok here is hint
\(\sum _{i=1}^{(40)}i^7 =0 \mod 5\)
\(\sum _{i=1}^{(40)}i^7 =0 \mod 2\)

Answer 39

but if you run the sum over integers that are relatively prime to 100, the remainder will be always 0 or -1 for all powers :

\[\sum \limits_{\gcd(i,100) = 1} i^{n} \pmod {100}\]

Answer 40

thats clever @Marki xD

\(5 \not |~ 7\) and \(2 \not | ~ 7\) so both sums evaluate to 0

Answer 41

how are you going to get to mod 100 from them ?

Answer 42

since gcd(2,5)=1
then
\(\sum _{i=1}^{(40)}i^7 =0 \mod 10\)

Answer 43

Yes

Answer 44

\(\sum _{i=1}^{(40)}i^7 =10k\)

Answer 45

yes thats the dead end.

Answer 46

:D
why dead we need to show k=10m :P

Answer 47

idk how ?

Answer 48

actually i did it with primitive roots as u did in last question

Answer 49

AHA! We can represent all the i's in terms of a basis: \[\Large i= a*10^1+b*10^0\] Raise this to the 7th power mod 100 we have: \[(a*10+b)^7 \mod 100 \equiv 70 ab^6 + b^7\]

Answer 50

lol i got stuck with my own solution :'(

Answer 51

We can already remove every multiple of 10 from the sum leaving us with 1 to 9, 11 to 19, etc... and representing it this way we really have: \[\sum_{i=1}^{40} 70ab^6+b^7= 70 \sum_{a=1}^3 \sum_{b=1}^9 ab^6 + 4 \sum_{b=1}^9 b^7\] This is feeling matrixy but the idea seems fairly simple, b is the first digit, and a is the second digit.

Answer 52

Expressed this way, it's obvious now that when a=2 and b=5 that we can drop out those terms from the first "double summation" since they will just be 70*2*5=700 which is 0 mod 100. \[\ 70 \sum_{b=1}^9( 1b^6+3b^6) + 4 \sum_{b=1}^9 b^7\] \[\ 280 \sum_{b=1}^9b^6 + 4 \sum_{b=1}^9 b^7\] \[\ 280 \left( \sum_{b=1}^4b^6+ \sum_{b=6}^9b^6 \right) + 4 \sum_{b=1}^9 b^7\] Then remembering this is mod 100, change the 280 into 80. \[\ 80 \left( \sum_{b=1}^4b^6+ \sum_{b=6}^9b^6 \right) + 4 \sum_{b=1}^9 b^7\] Actually I also noticed just now that when b is 5 it will give us 100 on the other b^7 summation too, so we can remove it there as well: \[\ 80 \left( \sum_{b=1}^4b^6+ \sum_{b=6}^9b^6 \right) + 4 \left( \sum_{b=1}^4b^7+ \sum_{b=6}^9b^7 \right)\]

Answer 53

We can recombine and factor around to get both summations like this: \[\Large 4 \sum_{b=1 \ or \ b=6}^{4 \ or \ 9}b^6(20+b) \] Which, let's be honest, is simple to calculate because it's only 8 terms.

Answer 54

:|

Answer 55

i was like gonna say there is no order 7 in modulo 100

Answer 56

@ganeshie8 right ?
so this equivalent work
\(r^{0.7}+r^{1.7} + r^{2.7} + \cdots + r^{7(\phi(100)-1)} = \dfrac{1-r^{(7(\phi(100) ) )}}{1-r^7} \equiv 0 \pmod {100}\)
but now not sure

Answer 57

Here is an insanely short solution :

\(\sum\limits_{i=1}^{40} i^7 \equiv \sum\limits_{i=1}^{40} i^3+5k\equiv \sum\limits_{i=1}^{40} i^3 \equiv 0 \pmod{5^2} \)

\(\sum\limits_{i=1}^{40} i^7 \equiv \sum\limits_{i=1}^{40} i \equiv 0 \pmod{2^2} \)

combining them gives
\(\sum\limits_{i=1}^{40} i^7 \equiv 0 \pmod {5^22^2}\)

XD

Answer 58

yeah

Answer 59

\[r^{0.7}+r^{1.7} + r^{2.7} + \cdots + r^{7(\phi(100)-1)} = \dfrac{1-r^{(7(\phi(100) ) )}}{1-r^7} \equiv 0 \pmod {100}\]

this is tricky business :
how do you know a primitive root exists for 100 ?
even if it exists, the bases in question {1,2,...,40} are not all relatively prime to 100. so your logic wont work.

Answer 60

cc ?

Answer 61

well hmm xD yeah i saw its wrong lately

Answer 62

did u get my previous solution, im in love wid fermat already xD

Answer 63

yes it was nice !!
first i thought like u
\(\sum _{i=1}^{\phi (n)} i^p \mod n ~~~~ \forall p<100\)

Answer 64

is zero , but then i dint know hw t pr0ve :|

Answer 65

it will be 0 or -1 if all the i's are relatively prime to 100

Answer 66

naa forget about -1 i found counter example xD

Answer 67

when ? it is an identity and we have proved it in your previous question

Answer 68

naa we proved Fermat sum ,not Euler sum

Answer 69

both are same
all you need to do is let the i's be relatively prime to 100

Answer 70

Below should be true whenever a primitive root exists for \(a\) :

\[
\begin{array}{}
\sum\limits_{\gcd(i,a)=1} i^n \equiv 0 \pmod a &:& \phi(a) \not |~ n \\~\\
\sum\limits_{\gcd(i,a)=1} i^n \equiv \phi(a) \pmod a &:& \phi(a) | n \\~\\

\end{array}

\]

Answer 71

notice when \(a\) is prime, you get the theorem that we proved in your previous question

Answer 72

let me know if u want a proof or examples

Answer 73

second part works but im nt convinced about the first one

Answer 74

https://www.wolframalpha.com/input/?i=%5Csum+_%7Bi%3D1%7D%5E%7B%2840%29%7Di%5E%7B80%7D+%28mod+100%29+++

Answer 75

gcd(i, 100) must be 1

you're running over first 40 positive integers, so obviously it wont work

Answer 76

maybe its like this
\(\begin{array}{}
\sum\limits_{\gcd(i,a)=1} i^n \equiv 0 \pmod a &:& \phi(a) \not |~ n \\~\\
\sum\limits_{\gcd(i,a)=1} i^n \equiv \phi(n) \pmod a &:& \phi(a) | n \\~\\

\end{array}\)

Answer 77

ok i'll work ltr on it , cya

Answer 78

Okay, il give you a chocolate if you find a counter example for above ^ :)

Answer 79

\[\ 80 \left( \sum_{b=1}^4b^6+ \sum_{b=6}^9b^6 \right) + 4 \left( \sum_{b=1}^4b^7+ \sum_{b=6}^9b^7 \right)\]

\[\sum_{b=1}^4 \left( 80b^6 + 4b^7 + 80(b+5)^6 + 4(b+5)^7\right)\]

@Kainui just 4 terms now :) and it does give correct answer after playing so much
https://www.wolframalpha.com/input/?i=%5Csum%5Climits_%7Bb%3D1%7D%5E4+%2880b%5E6%2B4b%5E7+%2B+80%28b%2B5%29%5E6+%2B+4%28b%2B5%29%5E7%29+mod+100

xD

Answer 80

chocolate idea excited me but u sound so sure (u dont seems like giving it ) :|
so i would believe u and say ok no counter example but u give me one true statement about it ok ?

Answer 81

why u add this "^" when u end a statement ? what does it even mean ?

Answer 82

@Kainui approach is amazing though

Answer 83

Back, my internet died right after I posted my answer. there's too much for me to read now, maybe when I wake up I'll read more lol.

Answer 84

@ganeshie8 which case work ?

Answer 85

Oh ganesh has a good idea! \[\Large 4 \sum_{b=1}^{4}b^6(20+b) + (b+5)^6(25+b) \] And yet more terms are cut out after distributing if you recognize the 25 and 4, so we have: \[\Large 4 \sum_{b=1}^{4}b^6(20+b) + b (b+5)^6 \] Expanding the binomial b+5 we see that the 5^2 terms will disappear as well! Getting warmer! \[\Large 4 \sum_{b=1}^{4}b^6(20+b) + b (b^6+6*5b^5)\] Redistribute and we have: \[\Large 4 \sum_{b=1}^{4}50b^6+2b^7\] And now we are left with just a few terms after seeing 4*50=0 mod 100..! (hope it's right XD) \[\Large 8 \sum_{b=1}^{4}b^7 = 8(1+2^7+3^7+4^7) \] But I still haven't reached the answer with this ridiculous wandering.Hmmm... Powers of 2 lol.

Answer 86

lol its like watching good match :P

Answer 87

like watching a good test match between australia and england :)

Answer 88

naa it would be boring :3 i mean real match

Answer 89

Hah! I'll take three of the terms and reverse their powers around into a mini geometric series! XD \[\large 1+2^7+4^7 = (2^7)^0+(2^7)^1+(2^7)^2 = \frac{(2^7)^3-1}{(2^7)-1}\] (we really should write this in base 2 shouldn't we I'll just look at the numerator since we? XD)

Here I just wrote the numerator since we know this is a whole number from the left that means this has a factor of 2^7-1 \[\large 2^{21}-1=111111111111111111111_2\]

Let's keep playing, I just thought I should share before I keep going wherever we end up @_@

Answer 90

So yeah on with it in base 2. XD \[\frac{111111111111111111111}{1111111}= \frac{1111111*100000010000001}{1111111} = \] \[\LARGE 100000010000001 = nevermind...\]

Answer 91

repunits are pretty neat stuff

2^7 = 28
so 1+2^7 + 4^7 = 1 + 28(1+28)

Answer 92

@ganeshie8 which case work ?

what are you refering to @Marki

Answer 93

nvm