The Prime Modulo

         Here we are, at the end of the chapter on number theory questions from Terry Tao's book! This also happens to be written few days before I have to go back to work, so chances are it will be the last in at least some time; we'll see! Without further ado:

         This is a special question. The asterisk on brackets means it's of a higher difficulty than other questions.  Perhaps because this is the first question of this level, we have a rather important hint given. 

I've already talked about my opinion of hints on this entry, so I won't repeat myself. However, the particular aspect of this hint is that unless you've gone a bit deeper into modular arithmetic or abstract algebra, you won't know what a generator is, or what  $\mathbb{Z} / p\mathbb{Z}$  stands for, or why  $a^k \not\equiv 1 \ [p]$. A quick google/wiki search will clarify things enough to use them, but it's the first question that requires this kind of knowledge.

In any case, I'll explain when they appear in my proof, so let's begin. Showing that the expression is divisible by $p$ is equivalent to showing that it is equal to $0$ (mod $p$). Keeping that in mind, let's take a look at the hint:

$a^k+(2a)^k+(3a)^k + \ldots + ((p-1)a)^k$

The most straightforward thing to do is to factorize it:

\[ \begin{equation} \label{(1)} a^k (1^k+2^k+3^k +\ldots + (p-1)^k) \end{equation} \]

At first glance none of this seems to help much, and in fact it just looks more complicated; althought we did manage to find the original expression. This is where understanding everything in the hint makes a difference:

         Putting some rigor aside, we can think of  $\mathbb{Z} / p\mathbb{Z}$  as being the set of integers (mod $p$):  $\{0,1,2, \ldots , p-1\}$. 

To say that $a$ generates  $\mathbb{Z} / p\mathbb{Z}$  means that  $an \in \mathbb{Z} / p\mathbb{Z}$  for all  $n \in \mathbb{Z} / p\mathbb{Z}$, and that  $an_1 = an_2 \implies n_1 = n_2$. 

In other words, multiplying every number in  $\{0,1,2, \ldots , p-1\}$ by $a$ will give us back the whole set. The number $a$ generates all of  $\mathbb{Z} / p\mathbb{Z}$  by adding itself repeatedly! We could think of it's action as a permutation of  $\mathbb{Z} / p\mathbb{Z}$.

The only thing we need to be careful with is that we don't know the actual permutation. For example, we could have $2a = 2$ or $3$ or $p-2$ for all we know. There are actually some constraints, but this is not important since we're looking at the sum of every element to the same power, so we know that regardless of how $a$ maps each element of  $\mathbb{Z} / p\mathbb{Z}$, the sum will be equal. This is what Terry calls "rearranging trick", and what gives us the following (after rearranging):

$a^k+(2a)^k+(3a)^k+\ldots + ((p-1)a)^k  \equiv  1^k+2^k+3^k +\ldots +(p-1)^k \ [p]$

So as not to make this too cumbersome, let  $S=1^k+2^k+\ldots + (p-1)^k$. By using our factorization $\eqref{(1)}$ on the left hand side, the above becomes:

$a^k S \equiv S \ [p]$

$a^k S - S \equiv 0 \ [p]$

$S (a^k-1) \equiv 0 \ [p]$

To finish, let's not forget that we are given that  $a^k \not\equiv 1 \ [p]$, which is equivalent to saying that  $a^k-1 \not\equiv 0 \ [p]$. This in turn implies that:

$S \equiv 0 \ [p]$

Concluding our proof.

That's how generators look like, I swear!

         There we have it! To be honest, at the start I wasn't too sure about this question. The hint is pretty strong, which is something I don't particularly like. In addition, as I mentioned at the beginning, a good portion of the readers would have to take by faith most things in the hint. 

It still is a bit too much of a hint imo, but after thinking about it for a bit, it seems fine for the purposes of this exercise. After all, if you don't know the existence of this type of things to begin with, it would be extremely difficult to figure out you could even do such a thing. I'm pretty sure there are other ways to prove this, but I doubt anything that doesn't require some knowledge beyond normal HS content.

        In a sense, I think the question actually succeeds in its objectives even more for people who don't have the knowledge. Being able to use certain facts and draw logical conclusions from them (regardless of the source of this knowledge) is a much more important skill than just knowing a lot. Even with these facts it's not a trivial question, although perhaps not an asterisk level one. In addition, anyone who has gone this far into the book will likely be just as curious to find out where all of this comes from, win-win! If I had to change anything in the question, I think I would omit the last sentence of the hint.

With this we have finished number theory! The next post will be about algebra and analysis, though I'm not sure when I will upload the first post. Good luck and keep solving!