How do you proof this?

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

1 Answer
Jun 20, 2018

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