Question

How do you proof this?

Let `f(n)=sum_(i,j=1)^ni^j`. where `n in NN`. Demonstrate that if `p` is a prime, then `f(p+1)` is a p multiple

Answer 1

Deleteable

Explanation:

`f(2 + 1) = sum_{i = 1}^3 sum_{j = 1}^3 i^j = 1^1 + 1^2 + 1^3 + 2^1 + 2^2 + 2^3 + 3^1 + 3^2 + 3^3 = 3 + 2 + 4 + 8 + 3 + 9 + 27 = 56`, multiple of `2`

`f(3 + 1) = f(3) + 4^1 + 4^2 + 4^3 + 1^4 + 2^4 + 3^4 + 4^4 = 56 + 4 + 16 + 64 + 1 + 16 + 81 + 256 = 494` multiple of `3`? No.

`f(5 + 1) = f(4) + 5^1 + 5^2 + 5^3 + 5^4 + 5^5 + 5^6 + 6^1 + 6^2 + 6^3 + 6^4 + 6^5 + 6^6 + 1^5 + 1^6 + 2^5 + 2^6 + 3^5 + 3^6 + 4^5 + 4^6 = 494+5+25+125+625+3125+15625+6+36+216+1296+7776+46656 + 1+1+32+64+243+729+1024+4096 = 82200`, multiple of `5`

You want me to prove that `f(p+1)/p in NN, forall p >= 5`

`f(p+1) equiv 0 mod p`

`f(5 + 1) = sum 1^i + sum 2^i + sum 3^i + sum 4^i + sum 5^i + sum 6^i`

`2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 = 2(1 - 2^6)/(1 - 2)`

`f(p + 1) = p + 1 + sum_{i = 2}^{p + 1} i (1- i^{p + 1})/(1 - i)`

Let's pass to modulo p, using `a^p equiv a^1 mod p`

`f(p + 1) equiv [1 + sum_{i = 2}^{p + 1} i (1- i^{1 + 1})/(1 - i)] mod p`

`f(p + 1) equiv [1 + sum_{i = 2}^{p + 1} i(i+1)] mod p`

`f(p + 1) equiv [sum_{i = 1}^{p + 1} i^2 + sum_{i = 2}^{p + 1} i ] mod p`

`f(p + 1) equiv ((p + 1)(p+2)(2p +3))/6 + ((p + 3)p)/2`

`(p^2 + 3p + 2)(2p + 3)`

`(2p^3 + 6p^2 + 4p) + (3p^2 + 9p + 6)`

`2p^3 + 9p^2 + 13p + 6`

`f(p + 1) equiv 6/6 = 1`