O PROBLEMĂ ... SATISFĂCĂTOARE // A Problem with... Much Satisfaction // Проблема с... большим удовлетворением

          I'm going back to the magazine from the previous post. 

Starting with this issue,  1 / 1979, a new column appears, PREPARATORY PROBLEMS FOR IMO (see pages 32-33). At that time, I was in my last year of High School and I decided (at the suggestion of a high school classmate, Mariana DIACONESCU) to enroll at the Faculty of Mathematics. 

     I think that during the summer vacation after my high school diploma, after I passed the college entrance exam, I tried my hand at these problems. Problem  O : 1  was a particular case of the article published in the same journal, on pages 5-7, and I imitated the solution there. Problem  O : 2  I didn't like at the time, so I moved on to  O : 3.

               "O : 3.  Let  $p$  be a prime number,  $p>2$ . For each number  $k$  from

  $1\; to\; p-1$ , we denote by  $a_k$  the remainder of the division of  $k^p\;by\;p^2$ .

                     Let it be shown as 

$$a_1+a_2+a_3+\dots+a_{p-1}=\frac{p^3-p^2}{2}$$

{Taken from : }( Kvant Magazine, issue 2 / 1978)

ANSWER  CiP

$$a_k+a_{p-k}=p^2\;\;\;\;\;,\;\;k=1,\;2,\;\dots,\;p-1 \tag {1}$$

                                         Solution CiP

               According to division with remainder we can write :

$k^p=A_k\cdot p^2+a_k\;\;\;,\;\;0<a_k<p^2\;\;\;\;,\;\;\;A_k\in\mathbb{N}\;\;,\;\;k=1,\;2,\;\dots\;, p-1 \tag{2}$

Since the number  $p$  is prime, we have  $p\not \mid k^p$   so  $a_k$  cannot be zero.

We can also write :

$(p-k)^p=A_{p-k}\cdot p^2+a_{p-k}\;\;\;,\;\;0<a_{p-k}<p^2 \tag{3}$

Adding the equations  (2)  and  (3)  we have :

$k^p+(p-k)^p=B_k\cdot p^2+(a_k+a_{p-k}) \tag{4}$

where  $B_k=A_k+A_{p-k}\in\mathbb{N}$. But, according to the binomial theorem :

$(p-k)^p=p^p-C_p^1\cdot p^{p-1}\cdot k+C_p^2\cdot p^{p-2}\cdot k^2-\dots -C_p^{p-2}\cdot p^2\cdot  k^{p-2}+C_p^{p-1}\cdot p\cdot k^{p-1}-k^p$

We denoted the binomial coefficients with  $C_p^k=\frac{p!}{k!\cdot (n-k)!}$, which in latex is denoted  $_p^k\textrm{C}$ , and in algebra  $\binom{p}{k}$.

Since  $C_p^{p-1}=p$ , we have from here

$k^p+(p-k)^p=\left [p^{p-2}-C_p^1p^{p-3}k+C_p^2p^{p-4}k^2-\dots -C_p^{p-2}k^{p-2}+k^{p-1} \right ]\cdot p^2$

so the left side of the equation  (4)  is divided by  $p^2$  and then on the right side we must have $p^2\mid (a_k+a_{p-k})$.  So

  $a_k+a_{p-k}=D\cdot p^2\;\;,\;\;D\in\mathbb{N} \tag{5}$

     But from the inequalities in  (2)  and  (3)  it follows  $0<a_k+a_{p-k}<2\cdot p^2$ . So in  (5)  we must have  $D=1$ , that is, precisely the formula  (1).

          Adding the  $p-1$  relations  (1)  we have, written from right to left :

$$(p-1)\cdot p^2=\sum_{k=1}^{p-1}(a_k+a_{p-k})=\sum_{k=1}^{p-1}a_k+\sum_{p-k=1}^{p-k=p-1}a_{p-k}=2\cdot \sum_{k=1}^{p-1}a_k$$

The formula in the problem is proven.

$\blacksquare\;\;\;\blacksquare$

          For example : 

$a_1=remainder\;1^7:49\;\;=1$

$a_2=remainder\;2^7:49\;\;=30$

$a_3=remainder\;3^7:49\;\;=31$

$a_4=remainder\;4^7:49\;\;=18$

$a_5=remainder\;5^7:49\;\;=19$

$a_6=remainder\;6^7:49\;\;=48$

and it is seen that  $a_1+a_6=a_2+a_5=a_3+a_4=49$.

$\square$

               REMARK CiP   This problem gave me a lot of satisfaction when I solved it. At first I tried different ways to approach it, without success. It was only after I did a numerical simulation with a pocket calculator (as in the example presented above) that I noticed the fulfillment of the relation  (1)  between the residues. I was delighted with the discovery I made. I was going to demonstrate it...The idea of ​​showing that we have D equal to 1 in the relation  (5)  was first encountered in Sierpinski (in Russian, in Romanian - at that time I could easily and long-term retain what I read). Today, it took me a few days to reconstruct the demonstration from back then.

     And, let's report another error. The problem had the number  M442 and was published in issue 5 / 1977 (page 20). In issue 2 / 1978 the solution was published (page 28).

<end REM>