A conjecture of the remainder of summary of a sequence of unified power numbers divided by a prime number While attending Sunday (Nov. 21st, 2015) "Math Counts Mock Comp" at Stuart County Day School in New Jersey, I was intrigued by one of the question:
“What is the remainder when $1^2+2^2+3^2+…+12^2$ is divided by 13?”
I converted the question into:
“What is the remainder when $1^2+2^2+3^2+4^2+5^2+6^2+(13-6)^2+(13-5)^2+(13-4)^2+(13-3)^2+(13-2)^2+(13-1)^2$ is divided by 13?”
Then with several more steps of deductions, the question transformed itself into:
“What is the remainder when $1^2+2^2+3^2+4^2+5^2+6^2$is divided by 13?”
The answer is $0$$ and I couldn’t help but notice that 13 is prime number.
After some thoughts and a C++ program I came up with a particular conjecture:
"When a prime number is expressed as $P = 2N + 1$ where $N \ge 2$, then the remainder when $1^2+2^2+3^2+…+N^2$ is divided by P is ALWAYS $0$!”
As a computer software engineer I was able to write a program to prove my conjecture up the first $9000$ prime numbers!
Since I am not a mathematician and there are infinite numbers of prime numbers, I couldn’t prove my conjecture in a scientific way and it bothers me.
I then further came up with a generic conjecture:
"When a prime number is expressed as $P = 2N + 1$ where $N \ge 3$, and $X$ is an even number, then the remainder when $1^X+2^X+3^X+…+N^X$ is divided by P is ALWAYS $0$!”
Running my C++ program I was able to prove of my conjecture up to the first $500$ prime numbers with the power $X$ as high as $6$!
I would appreciate if someone can shed some lights on my conjectures:


*

*Did any mathematician offer the same or similar conjectures before?

*Does the scientific proof of my conjecture(s) (or similar conjecture(s)) exist? And if it does, would you please email me a link of the proof?

 A: For the first conjecture, this is true for any odd $p$ that isn't divisible by $3$, it is not very closely related to primes.  This follows immediately from the fact that if $p = 2n+1$ and $3 \nmid p$ then $n(n+1)$ is divisible by $6$, so $n(n+1)(2n+1)/6$ (the exact formula for $1^2+\cdots +n^2$, known) is always a multiple of $2n+1$.  I would guess this was known to ancient Greeks.
For the second conjecture, this is very standard and classical (surely Euler would have "known", although it have taken until Gauss to prove that primitive roots exist).
First, we might as well take the sum all the way from $1$ up to $p-1$.  Since $x$ is even, this gives exactly twice the value of the sum from $1$ to $n$; since $p$ is odd, either sum will be zero precisely when the other one is.
So now, the following is well-known from elementary field theory:

$S(x) = 1^x + 2^x + \cdots + (p-1)^x \not\equiv 0 \pmod p$ if and only if $x$ is a multiple of $p-1$.

Proof: If $x$ is not a multiple of $p-1$ (for instance if $0 < x < p-1$), then take $g$ to be a primitive root mod $p$, so that $g^x \not\equiv 1 \pmod p$.  Since multiplication by $g$ permutes the elements of $(\mathbb Z/p\mathbb Z)^\times$, we have $$g^x \sum_{k=1}^{p-1} k^x = \sum_{k=1}^{p-1} (gk)^x \equiv \sum_{k=1}^{p-1} k^x \pmod p,$$
in other words $g^x S(x) \equiv S(x)$, or $(g^x - 1) S(x) \equiv 0 \pmod p$.  Since $g^x \not\equiv 1$, this forces $S(x)\equiv 0$.
Conversely, if $x$ is a multiple of $p-1$ then by Fermat's little theorem we have $S(x) \equiv -1 \pmod p$ since each term reduces to $1$.  In particular, your original sum is always congruent to either $(p-1)/2$ or $0$ depending on whether $x$ is divisible by $p-1$.
