2

Show that $1^{26} + 2^{26} + 3^{26} + \cdots + 26^{26} $ is divisible by $53$.

Inspired by another more basic question asked here... I'm interested to see what elegant proofs you come up with (and mine is also given below in an answer).

Community
  • 1
Joffan
  • 39,627
  • 1
    Perhaps you could tell us what elegant proofs you already know, so we don't waste everyone's time telling you things you already know. – Gerry Myerson Feb 18 '17 at 23:19
  • This appears to generalize to: $1^n + 2^n + \cdots + n^n$ is divisible by $2n+1$ if and only if $2n+1$ is a prime congruent to 1 mod 4. – Michael Lugo Feb 18 '17 at 23:25
  • @MichaelLugo I hope you'll be contributing an answer... – Joffan Feb 18 '17 at 23:34
  • 1
    @GerryMyerson Can you suggest how I could rephrase the question? I have my solution but I was interested to see what other creative solutions people could devise. – Joffan Feb 18 '17 at 23:51
  • What you could do is you could say, "here are all the proofs I know [your proofs go here]; what proofs can you add?" – Gerry Myerson Feb 19 '17 at 04:27

3 Answers3

2

First, let us note that $i^{2m}\equiv(53-i)^{2m}\bmod 53$. So $\sum_{k=1}^{26}k^{26}\equiv \sum_{k=27}^{52}k^{26}\bmod 53$. This means, $2\sum_{k=1}^{26}k^{26}\equiv \sum_{k=1}^{52}k^{26}\bmod 53$. If we can find $\sum_{k=1}^{52}k^{26}\bmod 53$, then we can also find $\sum_{k=1}^{26}k^{26}\bmod 53$.

Now, $53$ is a prime number, so it must have a primitive root. Let $g$ be a primitive root of $53$. That means $g^{52}\equiv 1\bmod 53$ and for no value $1\leq s \leq 51$ we can have $g^s\equiv1 \bmod 53$. Also, $(g^{26})^2\equiv1\bmod 53$. This means $53|(g^{26}+1)(g^{26}-1)$. But $53$ cannot divide $(g^{26}-1)$, because it would mean $g^{26}\equiv 1\bmod 53$ and $26<52$. That means, $53|(g^{26}+1)$, or $g^{26}\equiv -1\bmod 53$.

Now if we note that the numbers $g,g^2,g^3,...,g^{52}$ form a reduced residue system of $53$, we can write $\sum_{k=1}^{52}k^{26}\ \equiv \sum_{k=1}^{52}(g^{26})^k\equiv \sum_{k=1}^{52}(-1)^k \bmod 53$. In the last sum, the exponent of $(-1)$ will be even $26$ times and will be odd $26$ times. That means the sum will be $0\bmod 53$.

Now we have $2\sum_{k=1}^{26}k^{26}\equiv 0 \bmod 53$, so $\sum_{k=1}^{26} k^{26}\equiv 0\bmod 53$, as $(53,2)=1$ .

Joffan
  • 39,627
Mutasim Mim
  • 600
2

Let $ S $ be the given sum, and fix $ \alpha \in \mathbb F_{53}^{\times} $ such that $ \alpha $ is not a root of $ X^{26} - 1 $. Then, (the following equalities are in $ \mathbb F_{53} $)

$$ 2S = \sum_{k=1}^{52} k^{26} = \sum_{k=1}^{52} (\alpha k)^{26} = \alpha^{26} \cdot 2S $$

(Note that $ x \to \alpha x $ is a permutation of $ \mathbb F_{53} $.) It follows that either $ 1 - \alpha^{26} = 0 $ or $ S = 0 $. Since $ \alpha $ was chosen such that the former is not true, the latter must be true; i.e $ S \equiv 0 \pmod{53} $.

Ege Erdil
  • 17,747
  • 1
    $ \mathbb F_{53}^{\times} $ has $ 52 $ elements, and a polynomial of degree $ n $ can have at most $ n $ roots in a field; this means there are at least (in fact, exactly) $ 26 $ such $ \alpha $. – Ege Erdil Feb 19 '17 at 18:18
0

$53$ is a prime of the form $1 \bmod 4$. Consider a primitive root $g$ - this has quadratic residues at even powers and non-residues at odd powers. So we know that $-1$ is a quadratic residue, and thus for any $x$ a quadratic residue, $-x$ is also. Also since exactly half the totients of $53$ are quadratic residues, we must have that half the numbers in $\{1,2,\ldots,26\}$ are quadratic residues and half are quadratic non-residues. For a quadratic residue $q$, $q^{26}\equiv 1 \bmod 53$ and for a quadratic non-residue $n$, $n^{26}\equiv -1 \bmod 53$.

Thus we have $1^{26} + 2^{26} + 3^{26} + \cdots + 26^{26} \equiv 13\cdot1 + 13\cdot -1 \equiv 0 \bmod 53$

Joffan
  • 39,627