Darij's posts on the PEN forum:
(This forum has been formerly hosted at http://www.problem-solving.be/pen/ , where some of these posts can also be found - sometimes in OUTDATED versions.)

This file contains the source code of all of my mathematical posts on the PEN forum. I have decided to upload this on my website because the PEN forum, unfortunately, does not have the best server of the world and is sometimes difficult to access.

Darij Grinberg

----------------------------------------------------------------------------------------------------------------------------

Note that the set $\mathbb{N}$ of natural numbers is defined as $\mathbb{N}=\left\{1,2,3,...\right\}$ throughout PEN.

----------------------------------------------------------------------------------------------------------------------------

http://www.problem-solving.be/pen/viewtopic.php?t=346
Problem I 11

[quote="Peter"]Let $p$ be a prime number of the form $4k+1$. Show that $$\sum^{p-1}_{i=1} \left( \left \lfloor \frac{2i^2}{p} \right \rfloor - 2\left \lfloor \frac{i^2}{p} \right \rfloor \right) = \frac{p-1}{2}.$$[/quote]

Lemma 1 from http://www.mathlinks.ro/Forum/viewtopic.php?t=150711 (or http://www.problem-solving.be/pen/viewtopic.php?t=345 ) states:

[b]Lemma 1.[/b] For any integer $n$ and any non-integer real number $a$, we have $\lfloor a \rfloor + \lfloor n-a \rfloor = n-1$.

Now, since $p$ is a prime number of the form $4k+1$, it is known that $-1$ is a quadratic residue modulo $p$. Thus, there exists an integer $\lambda$ such that $\lambda^2\equiv -1\text{ mod }p$. Now, $p\nmid\lambda$ (because else, we would have $\lambda^2\equiv 0\text{ mod }p$, contradicting $\lambda^2\equiv -1\text{ mod }p$). Therefore, multiplication with $\lambda$ is a permutation of the nonzero residues modulo $p$. In other words, if we define a function $L$ from $\left\{1;\;2;\;...;\;p-1\right\}$ to $\left\{1;\;2;\;...;\;p-1\right\}$ by letting $L\left(i\right)$ be the remainder of $\lambda i$ upon division by $p$ for every $i\in\left\{1;\;2;\;...;\;p-1\right\}$, then this function $L$ is a permutation of $\left\{1;\;2;\;...;\;p-1\right\}$. Thus,

[color=green][b](1)[/b][/color] $\sum^{p-1}_{i=1} \left( \left \lfloor \frac{2i^2}{p} \right \rfloor - 2\left \lfloor \frac{i^2}{p} \right \rfloor \right) = \sum^{p-1}_{i=1} \left( \left \lfloor \frac{2\left(L\left(i\right)\right)^2}{p} \right \rfloor - 2\left \lfloor \frac{\left(L\left(i\right)\right)^2}{p} \right \rfloor \right)$.

Now, for every $i\in\left\{1;\;2;\;...;\;p-1\right\}$, both integers $i^2$ and $2i^2$ are coprime with $p$ (since $i$ is coprime with $p$ because $p$ is a prime and $1\leq i 1, then the number$\Phi_3\left(x\right)$is a proper divisor of$\Phi_3\left(x^k\right)$. In fact, since x is an integer and$\Phi_3$and u are polynomials with integer coefficients, the equation$\Phi_3\left(x^k\right)=u\left(x\right)\cdot \Phi_3\left(x\right)$yields that the number$\Phi_3\left(x\right)$divides the number$\Phi_3\left(x^k\right)$, and in fact it is a proper divisor since it is not equal to 1 (in fact,$\Phi_3\left(x\right)=x^2+x+1>1$) and not equal to$\Phi_3\left(x^k\right)$(since$\Phi_3\left(x\right)=x^2+x+1<\left(x^k\right)^2+x^k+1=\Phi_3\left(x^k\right)$). Now, if the number n is not a power of 3, then it has a prime divisor$\neq 3$. Let q be this prime divisor. Then, q is a positive integer, q > 1 (since q is a prime), and q is not divisible by 3 (since q is a prime$\neq 3$), and also, the number n can be written in the form n = qr, where r is some positive integer. Hence, by the above, the number$\Phi_3\left(2^r\right)$is a proper divisor of$\Phi_3\left(\left(2^r\right)^q\right)$. Thus,$\Phi_3\left(\left(2^r\right)^q\right)$cannot be a prime. But$\Phi_3\left(\left(2^r\right)^q\right)=\Phi_3\left(2^{qr}\right)=\Phi_3\left(2^n\right)=\left(2^n\right)^2+2^n+1=1^n+2^n+4^n$must be a prime by the condition of the problem. Hence, n must be a power of 3. That's all. darij ---------------------------------------------------------------------------------------------------------------------------- http://www.problem-solving.be/pen/viewtopic.php?t=556 http://www.mathlinks.ro/Forum/viewtopic.php?t=150922 Problem P 20 [quote="Peter"]If an integer$n$is such that$7n$is the form$a^2 +3b^2$, prove that$n$is also of that form.[/quote] In fact, let$A$and$B$be two integers satisfying$7n=A^2+3B^2$. Then,$7\mid A^2+3B^2$, so that also$7\mid\left(A^2+3B^2\right)-7B^2=A^2-4B^2=\left(A+2B\right)\left(A-2B\right)$. Thus, since$7$is prime, we have$7\mid A+2B$or$7\mid A-2B$. If$7\mid A+2B$, then$\frac{A+2B}{7}$is an integer; then, by writing$\left(2\cdot\frac{A+2B}{7}-B\right)^2+3\left(\frac{A+2B}{7}\right)^2=\frac{A^2+3B^2}{7}=\frac{7n}{7}=n$, we obtain a representation of$n$in the form$a^2+3b^2$. If$7\mid A-2B$, then$\frac{A-2B}{7}$is an integer; then, by writing$\left(2\cdot\frac{A-2B}{7}+B\right)^2+3\left(\frac{A-2B}{7}\right)^2=\frac{A^2+3B^2}{7}=\frac{7n}{7}=n$, we obtain a representation of$n$in the form$a^2+3b^2$. In both cases, we have seen that$n$can be represented in the form$a^2+3b^2$. This completes the solution. Darij ---------------------------------------------------------------------------------------------------------------------------- http://www.problem-solving.be/pen/viewtopic.php?t=618 http://www.mathlinks.ro/Forum/viewtopic.php?t=150984 Problem S 14 [quote="Peter"]Let$p$be an odd prime. Determine positive integers$x$and$y$for which$x \le y$and$\sqrt{2p}-\sqrt{x}-\sqrt{y}$is nonnegative and as small as possible.[/quote] Copying [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=48300]my solution from MathLinks[/url]: Can anyone check my solution below? It looks very different from the proposed solution, it has less ugly computations than the proposed solution, and it uses the primality of p only at the very end (it wouldn't use it at all if we would replace "non-negative" by "positive" in the condition of the problem), so I am wondering whether it can be correct... [color=blue][b]Problem.[/b] Let p be an odd prime. Determine the positive integers x and y with$x\leq y$for which the number$\sqrt{2p}-\sqrt{x}-\sqrt{y}$is non-negative and as small as possible.[/color] [i]Solution.[/i] We claim that the required integers x and y are$x=\frac{p-1}{2}$and$y=\frac{p+1}{2}$. In fact, first note that$\left(\sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}\right)^{2}=\frac{p-1}{2}+\frac{p+1}{2}+2\cdot\sqrt{\frac{p-1}{2}}\cdot\sqrt{\frac{p+1}{2}}=p+\sqrt{\left(p-1\right)\left(p+1\right)}=p+\sqrt{p^{2}-1}$. Now,$\frac{p-1}{2}$and$\frac{p+1}{2}$are integers (since p is odd, and thus p - 1 and p + 1 are even), and$\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$is indeed non-negative (this is equivalent to$\sqrt{2p}\geq\sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ 2p\geq\left(\sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}\right)^{2}\Longleftrightarrow\ \ \ \ \ 2p\geq p+\sqrt{p^{2}-1}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ p\geq\sqrt{p^{2}-1}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ p^{2}\geq p^{2}-1$, what is true). So it remains to prove that$\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$is indeed the smallest possible nonnegative sum of the form$\sqrt{2p}-\sqrt{x}-\sqrt{y}$for positive integers x and y with$x\leq y$and achieved only for$x=\frac{p-1}{2}$and$y=\frac{p+1}{2}$. In order to prove this, we assume that x and y are positive integers with$x\leq y$and$0\leq\sqrt{2p}-\sqrt{x}-\sqrt{y}\leq\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$. If we succeed to show that$x=\frac{p-1}{2}$and$y=\frac{p+1}{2}$, then we will be done. The inequality chain$0\leq\sqrt{2p}-\sqrt{x}-\sqrt{y}\leq\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$rewrites as$\sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}\leq\sqrt{x}+\sqrt{y}\leq\sqrt{2p}$. We square this inequality (it's not the time to worry about positive and negative yet ;) ):$\left(\sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}\right)^{2}\leq\left(\sqrt{x}+\sqrt{y}\right)^{2}\leq 2p\Longleftrightarrow\ \ \ \ \ p+\sqrt{p^{2}-1}\leq x+y+2\cdot\sqrt{x}\cdot\sqrt{y}\leq 2p$. Now, we have$x+y\sqrt{p^{2}-2p+1}=p-1$, this yields$x+y>\frac12\left(p+\left(p-1\right)\right)=p-\frac12$, and thus, since x and y are integers, this entails$x+y\geq p$. So we have$p\leq x+y<2p$. Thus, x + y = p + s for some integer s satisfying$0\leq s\leq p-1$. Denoting x - y = k, we note that$k\leq 0$(since$x\leq y$) and$x=\frac{x+y}{2}+\frac{x-y}{2}=\frac{p+s}{2}+\frac{k}{2}$and$y=\frac{x+y}{2}-\frac{x-y}{2}=\frac{p+s}{2}-\frac{k}{2}$. Hence,$p+\sqrt{p^{2}-1}\leq x+y+2\cdot\sqrt{x}\cdot\sqrt{y}\leq 2p$becomes$p+\sqrt{p^{2}-1}\leq p+s+2\cdot\sqrt{\frac{p+s}{2}+\frac{k}{2}}\cdot\sqrt{\frac{p+s}{2}-\frac{k}{2}}\leq 2p\Longleftrightarrow\ \ \ \ \ p+\sqrt{p^{2}-1}\leq p+s+\sqrt{\left(p+s+k\right)\left(p+s-k\right)}\leq 2p\Longleftrightarrow\ \ \ \ \ \sqrt{p^{2}-1}-s\leq\sqrt{\left(p+s+k\right)\left(p+s-k\right)}\leq p-s$(we subtracted p + s from the last inequality chain)$\Longleftrightarrow\ \ \ \ \ \sqrt{p^{2}-1}-s\leq\sqrt{\left(p+s\right)^{2}-k^{2}}\leq p-s$. Since$\sqrt{p^{2}-1}>\sqrt{p^{2}-2p+1}=p-1\geq s$, the left hand side of this inequality,$\sqrt{p^{2}-1}-s$, is positive; thus, we can square this inequality:$\left(\sqrt{p^{2}-1}-s\right)^{2}\leq\left(p+s\right)^{2}-k^{2}\leq\left(p-s\right)^{2}\Longleftrightarrow\ \ \ \ \ \left(p^{2}-1\right)+s^{2}-2\sqrt{p^{2}-1}\cdot s\leq p^{2}+s^{2}+2ps-k^{2}\leq p^{2}+s^{2}-2ps\Longleftrightarrow\ \ \ \ \;-1-2\sqrt{p^{2}-1}\cdot s\leq 2ps-k^{2}\leq-2ps\Longleftrightarrow\ \ \ \ \ 1+2\sqrt{p^{2}-1}\cdot s\geq k^{2}-2ps\geq 2ps\Longleftrightarrow\ \ \ \ \ 1+2\sqrt{p^{2}-1}\cdot s+2ps\geq k^{2}\geq 4ps$. Since$\sqrt{p^{2}-1}<\sqrt{p^{2}}=p$, we even have$1+2p\cdot s+2ps>k^{2}\geq 4ps\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ 1+4ps>k^{2}\geq 4ps$. Since$k^{2}$is an integer, we thus have$k^{2}=4ps$. Thus,$p\mid k^{2}$, what, since p is prime, yields$p\mid k$, so that$p^{2}\mid k^{2}$. Thus,$p^{2}\mid 4ps$, so that$p\mid 4s$. Since p is odd, this yields$p\mid s$. Since$0\leq s\leq p-1$, this leads to s = 0, and thus$x=\frac{p+s}{2}+\frac{k}{2}=\frac{p}{2}+\frac{k}{2}$and$y=\frac{p+s}{2}-\frac{k}{2}=\frac{p}{2}-\frac{k}{2}$. Now,$\left(\sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}\right)^{2}\leq\left(\sqrt{x}+\sqrt{y}\right)^{2}\Longleftrightarrow\ \ \ \ \ \left(\sqrt{\frac{p-1}{2}}+\sqrt{\frac{p+1}{2}}\right)^{2}\leq\left(\sqrt{\frac{p}{2}+\frac{k}{2}}+\sqrt{\frac{p}{2}-\frac{k}{2}}\right)^{2}\Longleftrightarrow\ \ \ \ \ \left(\sqrt{p-1}+\sqrt{p+1}\right)^{2}\leq\left(\sqrt{p+k}+\sqrt{p-k}\right)^{2}\Longleftrightarrow\ \ \ \ \ \left(p-1\right)+\left(p+1\right)+2\cdot\sqrt{p-1}\cdot\sqrt{p+1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \leq\left(p+k\right)+\left(p-k\right)+2\cdot\sqrt{p+k}\cdot\sqrt{p-k}\Longleftrightarrow\ \ \ \ \ 2p+2\sqrt{p^{2}-1}\leq 2p+2\sqrt{p^{2}-k^{2}}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ 1\geq k^{2}$. Since k is an integer and$k\leq 0$, this yields either k = 0 or k = -1. For k = 0, we have$x=\frac{p}{2}+\frac{k}{2}=\frac{p}{2}$, what is impossible, since p is odd and x must be an integer. Thus, k = -1, so that$x=\frac{p}{2}+\frac{k}{2}=\frac{p-1}{2}$and$y=\frac{p}{2}-\frac{k}{2}=\frac{p+1}{2}$, and the problem is solved. Oh dear, you are still reading this here? I apologize for being even more boring than usual, but I tried to write every single step to find a mistake. I don't see any. Do you? darij ---------------------------------------------------------------------------------------------------------------------------- http://www.problem-solving.be/pen/viewtopic.php?t=136 http://www.mathlinks.ro/Forum/viewtopic.php?t=150502 Problem D 2 [quote="Peter"]Suppose that$p$is an odd prime. Prove that $$\sum_{j=0}^p \binom{p}{j} \binom{p+j}{j} \equiv 2^p + 1\pmod{p^2}.$$[/quote] For any integer$j$with$1\leq j\leq p-1$, we have$\binom{p+j}{j}\cdot j!=\frac{\left(p+j\right)\cdot\left(\left(p+j\right)-1\right)\cdot ...\cdot\left(\left(p+j\right)-j+1\right)}{j!}\cdot j!=\left(p+j\right)\cdot\left(\left(p+j\right)-1\right)\cdot ...\cdot\left(\left(p+j\right)-j+1\right)=\left(p+j\right)\cdot\left(p+j-1\right)\cdot ...\cdot\left(p+1\right)\equiv j\cdot\left(j-1\right)\cdot ...\cdot 1=j!\text{ mod }p$, and since$j!$is coprime to$p$(since$j!=1\cdot 2\cdot ...\cdot j$, and each of the numbers$1$,$2$, ...,$j$is coprime to$p$because$p$is prime and$j1$. Thus, the number$p^{p-1}+p^{p-2}+...+p+1$has a prime factor$q$. Then, since$p^p-1=\left(p-1\right)\left(p^{p-1}+p^{p-2}+...+p+1\right)$, we also have$q\mid p^p-1$, so that$p^p\equiv 1\text{ mod }q$. Hence,$p$is divisible by$\text{ord}_q p$. Since$p$is a prime, this yields that$\text{ord}_q p=1$or$\text{ord}_q p=p$. If$\text{ord}_q p=1$, then$p\equiv 1\text{ mod }q$, and thus$p^{p-1}+p^{p-2}+...+p+1\equiv 1^{p-1}+1^{p-2}+...+1+1=p\equiv 1\text{ mod }q$, what contradicts$q\mid p^{p-1}+p^{p-2}+...+p+1$. Hence,$\text{ord}_q p=1$is not possible, so we must have$\text{ord}_q p=p$. Since$\text{ord}_q p\mid q-1$(because$q$is a prime), this yields$p\mid q-1$, so that$q\equiv 1\mod p$. Since$q$is prime and divides$p^p-1$, it thus follows that$q$is a prime factor of$p^p-1$which is congruent to$1$modulo$p$, and we are done. darij ---------------------------------------------------------------------------------------------------------------------------- http://www.problem-solving.be/pen/viewtopic.php?t=151 http://www.mathlinks.ro/Forum/viewtopic.php?t=150517 Problem D 17 [quote="Peter"]Determine all positive integers$n$such that$ xy+1 \equiv 0 \; \pmod{n} $implies that$ x+y \equiv 0 \; \pmod{n}$.[/quote] In order to fill the ??? in the source: This is part [b](b)[/b] of AMM problem S 9 [1979, 306] by M. S. Klamkin and A. Liu. Reference from JSTOR: Solutions of Problems Dedicated to Emory P. Starke S9 M. S. Klamkin; A. Liu; Arnold Adelberg; Jeffrey M. Cohen The American Mathematical Monthly, Vol. 87, No. 6. (Jun. - Jul., 1980), p. 488. For the sake of completeness, part [b](a)[/b] states that: Determine all positive integers$n$such that$\gcd\left(x,n\right)=1$implies that$x^2\equiv 1\pmod n$. Darij ---------------------------------------------------------------------------------------------------------------------------- http://www.problem-solving.be/pen/viewtopic.php?t=347 http://www.mathlinks.ro/Forum/viewtopic.php?t=150713 Problem I 12 [quote="Peter"]Let$p=4k+1$be a prime. Show that $$\sum^{k}_{i=1} \left \lfloor \sqrt{ ip } \right \rfloor = \frac{p^2 -1}{12}.$$[/quote] A convention first: If$\mathcal{A}$is an assertion, then we denote by$\left[  \mathcal{A}\right]  $the logical value of the assertion$\mathcal{A}$, defined by$\left[  \mathcal{A}\right]  =\left\{ \begin{array}{c} 1\text{, if }\mathcal{A}\text{ is true};\\ 0\text{, if }\mathcal{A}\text{ is false}\end{array} \right.  $. Then, if$X$is a set and$Y$is a finite subset of$X$, then the number of elements of$Y$equals$\left\vert Y\right\vert =\sum_{x\in X}\left[  x\in Y\right]  $. This equation makes sense even if$X$is an infinite set, because the sum$\sum_{x\in X}\left[  x\in Y\right]  $may have infinitely many terms, but only finitely many of them are nonzero - namely, those corresponding to$x$being element of$Y$(and$Y$has finitely many elements). Let$u$be a nonnegative real. Applying the equation$\left\vert Y\right\vert =\sum_{x\in X}\left[  x\in Y\right]  $to$X=\mathbb{N}$and$Y=\left\{ t\in\mathbb{N}\mid t\leq u\right\}  $, we see that$\left\vert \left\{ x\in\mathbb{N}\mid x\leq u\right\}  \right\vert =\sum_{x\in\mathbb{N}}\left[ x\in\left\{  t\in\mathbb{N}\mid t\leq u\right\}  \right]  $. This simplifies to$\left\vert \left\{  x\in\mathbb{N}\mid x\leq u\right\}  \right\vert =\sum_{x\in\mathbb{N}}\left[  x\leq u\right]  $. But since$u$is nonnegative,$\left\vert \left\{  x\in\mathbb{N}\mid x\leq u\right\}  \right\vert =\left\lfloor u\right\rfloor $. Thus, we have proven that [color=green][b](1)[/b][/color]$\left\lfloor u\right\rfloor =\sum_{x\in\mathbb{N}}\left[  x\leq u\right]  $for every nonnegative real$u$. Thus, for each integer$i$with$1\leq i\leq k$, we have [color=green][b](2)[/b][/color]$\left\lfloor \sqrt{ip}\right\rfloor =\sum_{x\in\mathbb{N}}\left[  x\leq\sqrt{ip}\right]  =\sum_{x\in\mathbb{N}}\left[  x^{2}\leq ip\right]  $. Now,$i\leq k$yields$ip\leq kp$. Hence, if$x$is an integer such that$x\geq2k+1$, then$x^{2}\geq\left(  2k+1\right)  ^{2}=4k^{2}+4k+1>4k^{2}+k=k\left(  4k+1\right)  =kp\geq ip$, so that$x^{2}\leq ip$cannot hold, and thus we have$\left[  x^{2}\leq ip\right]  =0$. Thus,$\sum_{x\in\mathbb{N}}\left[  x^{2}\leq ip\right]  =\sum_{x=1}^{2k}\left[ x^{2}\leq ip\right]  $(because all the terms$\left[  x^{2}\leq ip\right]  $for$x\geq2k+1$are$=0$). Combining this with [color=green][b](2)[/b][/color], we get$\left\lfloor \sqrt{ip}\right\rfloor =\sum_{x=1}^{2k}\left[  x^{2}\leq ip\right]  $. Now, for any integer$x$with$1\leq x\leq2k$, we have$\left[  x^{2}\leq ip\right]  =1-\left[  x^{2}\geq ip\right]  $, because the assertion$x^{2}\leq ip$holds if and only if the assertion$x^{2}\geq ip$does not hold (in fact,$x^{2}=ip$cannot hold, since$x$is coprime with$p$, because$p$is a prime and$1\leq x\leq2k<4k+1=p$). Thus,$\left\lfloor \sqrt{ip}\right\rfloor =\sum_{x=1}^{2k}\left[  x^{2}\leq ip\right]  =\sum_{x=1}^{2k}\left(  1-\left[  x^{2}\geq ip\right]  \right)  =2k-\sum_{x=1}^{2k}\left[  x^{2}\geq ip\right]  =2k-\sum_{x=1}^{2k}\left[ i\leq\frac{x^{2}}{p}\right]  $(since$x^{2}\geq ip$is equivalent to$i\leq\frac{x^{2}}{p}$). Consequently,$\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =\sum_{i=1}^{k}\left( 2k-\sum_{x=1}^{2k}\left[  i\leq\frac{x^{2}}{p}\right]  \right) =k\cdot2k-\sum_{i=1}^{k}\sum_{x=1}^{2k}\left[  i\leq\frac{x^{2}}{p}\right]  =2k^{2}-\sum_{x=1}^{2k}\sum_{i=1}^{k}\left[  i\leq\frac{x^{2}}{p}\right]  $. Now, for any integer$x$with$1\leq x\leq2k$, we have$x^{2}\leq\left( 2k\right)  ^{2}=k\cdot4kk$, we have$\frac{x^{2}}{p}k$are$=0$). Thus,$\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =2k^{2}-\sum_{x=1}^{2k} \sum_{i=1}^{k}\left[  i\leq\frac{x^{2}}{p}\right]  =2k^{2}-\sum_{x=1}^{2k}\sum_{i\in\mathbb{N}}\left[  i\leq\frac{x^{2}} {p}\right]  =2k^{2}-\sum_{x=1}^{2k}\left\lfloor \frac{x^{2}}{p}\right\rfloor $(after [color=green][b](1)[/b][/color] applied to$u=\frac{x^{2}}{p}$). Since$p=4k+1$, we have$k=\frac{p-1}{4}$and$2k=\frac{p-1}{2}$, so this becomes$\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =2\left(  \frac{p-1} {4}\right)  ^{2}-\sum_{x=1}^{\left(  p-1\right)  /2}\left\lfloor \frac{x^{2} }{p}\right\rfloor $. Now, according to formula [color=green][b](5)[/b][/color] in http://www.mathlinks.ro/Forum/viewtopic.php?t=150712 (or http://www.problem-solving.be/pen/viewtopic.php?t=346 ), post #2, Theorem 2, we have$\sum_{x=1}^{\left(  p-1\right)  /2}\left\lfloor \frac{x^{2}} {p}\right\rfloor =\frac{\left(  p-1\right)  \left(  p-5\right)  }{24}$, so that$\sum_{i=1}^{k}\left\lfloor \sqrt{ip}\right\rfloor =2\left(  \frac{p-1} {4}\right)  ^{2}-\frac{\left(  p-1\right)  \left(  p-5\right)  } {24} =\frac{p^{2}-1}{12}$, qed. [b]PS.[/b] This problem has been also discussed at http://www.mathlinks.ro/Forum/viewtopic.php?t=5928 . Darij ---------------------------------------------------------------------------------------------------------------------------- http://www.problem-solving.be/pen/viewtopic.php?t=68 http://www.mathlinks.ro/Forum/viewtopic.php?t=150434 Problem A 66 I rename$s$into$t$: [quote="Peter"](Four Number Theorem) Let$a, b, c,$and$d$be positive integers such that$ab=cd$. Show that there exists positive integers$p, q, r,t$such that $$a=pq, \;\; b=rt, \;\; c=pt, \;\; d=qr.$$[/quote] Let$p=\gcd\left(a,\ c\right)$. Then,$p\mid a$and$p\mid c$. Define$q=\frac{a}{p}$and$t=\frac{c}{p}$; then,$q$and$t$are positive integers. Then,$a=pq$and$c=pt$. Hence,$ab=cd$becomes$pqb=ptd$, so that$qb=td$. The numbers$q$and$t$are coprime (in fact,$p=\gcd\left(a,\ c\right)=\gcd\left(pq,\ pt\right)=p\gcd\left(q,\ t\right)$yields$\gcd\left(q,\ t\right)=1$). Now,$qb=td$yields$t\mid qb$. Since$q$and$t$are coprime, this leads to$t\mid b$. Define$r=\frac{b}{t}$; then,$r$is a positive integer, and$b=rt$. Finally,$ab=cd$yields$d=\frac{ab}{c}=\frac{pq\cdot rt}{pt}=qr$. Thus, our four positive integers$p$,$q$,$r$,$t$satisfy$a=pq, \;\; b=rt, \;\; c=pt,  \;\; d=qr$. Hence, we are done. Darij ---------------------------------------------------------------------------------------------------------------------------- http://www.problem-solving.be/pen/viewtopic.php?t=25 OLD VERSION http://www.mathlinks.ro/Forum/viewtopic.php?t=150391 OLD VERSION Problem A 23 [quote="Peter"](Wolstenholme's Theorem) Prove that if $$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$$ is expressed as a fraction, where$p \ge 5$is a prime, then$p^2$divides the numerator.[/quote] This is mostly a copy of [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=46121]a MathLinks post of mine[/url], and I am submitting it here since I will refer to it in a number of other proofs. I will generalize the problem, but first I explain some preliminaries about primes. [color=blue][b]1. p-adic evaluation[/b][/color] Let p be an arbitrary prime. We denote by$\mathbb{Z}_{p}$the field of residues of integers modulo p. For any rational number x, we will now define a so-called [i]p-adic evaluation of x[/i]. This evaluation will be denoted by$v_{p}\left(x\right)$, and it is defined as follows: If$x\neq 0$, then$v_{p}\left(x\right)$is the greatest integer k such that$\frac{x}{p^k}$can be written as a fraction of two integers with the denominator not being divisible by$p$. Besides, we set$v_{p}\left(0\right)=+\infty$, where$+\infty$is just a symbol satisfying$+\infty>a$and$+\infty+a=+\infty$for any integer$a$(what we will mainly need is that$v_{p}\left(0\right)>v_{p}\left(x\right)$for any nonzero x). We can easily see how to compute$v_{p}\left(x\right)$for rationals$x\neq 0$: If x is a nonzero integer, then$v_{p}\left(x\right)$is the greatest integer k such that$p^{k}$divides x (particularly,$v_{p}\left(x\right)=0$if p doesn't divide x); if x is a fraction of two nonzero integers, say$x=\frac{a}{b}$with integers a and b, then$v_{p}\left(x\right)=v_{p}\left(a\right)-v_{p}\left(b\right)$. Note that there is a simple way to interpret the sign of the p-adic evaluation$v_{p}\left(x\right)$of a rational number x: If we write x as a reduced fraction (i. e. a fraction with numerator and denominator coprime; if x is an integer, then just write it in the form$x=\frac{x}{1}$), and it turns out that the numerator is divisible by p, then$v_{p}\left(x\right)>0$; if neither the numerator nor the denominator is divisible by p, then$v_{p}\left(x\right)=0$; if the denominator is divisible by p, then$v_{p}\left(x\right)<0$. It is rather easy to prove that for any two rational numbers x and y, we have$v_{p}\left(xy\right)=v_{p}\left(x\right)+v_{p}\left(y\right)$and$v_{p}\left(x+y\right)\geq\min\left(v_{p}\left(x\right);\;v_{p}\left(y\right)\right)$. [color=blue][b]2. Working with fractions modulo p[/b][/color] We will also need some familiarity with fractions in$\mathbb{Z}_{p}$. The main idea is to extend the notion of congruence modulo p from integers to rational numbers with nonnegative p-adic evaluation: If x and y are two rational numbers such that$v_{p}\left(x\right)\geq 0$and$v_{p}\left(y\right)\geq 0$, then we say that$x\equiv y\mod p$if and only if$v_{p}\left(x-y\right)>0$. Thus we have defined an equivalence relation (that it is an equivalence relation is easy to prove - do it for yourself) on the set of all rational numbers with nonnegative p-adic evaluation. Now one could expect that, in this way, we would obtain a kind of new group of remainders, say$\mathbb{Q}_{p}$- but in fact, we get nothing but our old familiar$\mathbb{Z}_{p}$, since for every rational number x, there is one and only one integer n satisfying$0\leq n 2 (since $p\geq u+3$). We start with the Gauss trick:

$2\sum_{k=1}^{p-1}\frac{1}{k^{u}}=\sum_{k=1}^{p-1}\frac{1}{k^{u}}+\sum_{k=1}^{p-1}\frac{1}{\left(p-k\right)^{u}}=\sum_{k=1}^{p-1}\left(\frac{1}{k^{u}}+\frac{1}{\left(p-k\right)^{u}}\right)=\sum_{k=1}^{p-1}\frac{k^{u}+\left(p-k\right)^{u}}{k^{u}\left(p-k\right)^{u}}$.

Using the fact that u is odd, we can expand $\left(p-k\right)^{u}$ according to the binomial formula:

$2\sum_{k=1}^{p-1}\frac{1}{k^{u}}=\sum_{k=1}^{p-1}\frac{k^{u}+\left(p^{u}-up^{u-1}k\pm ...+upk^{u-1}-k^{u}\right)}{k^{u}\left(p-k\right)^{u}}=\sum_{k=1}^{p-1}\frac{p^{u}-up^{u-1}k\pm ...+upk^{u-1}}{k^{u}\left(p-k\right)^{u}}$.

All terms of the numerator are divisible by p, so we can pull p out of the sum:

$2\sum_{k=1}^{p-1}\frac{1}{k^{u}}=p\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}$.

But since p > 2, we have $v_{p}\left(2\right)=0$, so that

$v_{p}\left(2\sum_{k=1}^{p-1}\frac{1}{k^{u}}\right)=v_{p}\left(2\right)+v_{p}\left(\sum_{k=1}^{p-1}\frac{1}{k^{u}}\right)=v_{p}\left(\sum_{k=1}^{p-1}\frac{1}{k^{u}}\right)$.

On the other hand,

$v_{p}\left(2\sum_{k=1}^{p-1}\frac{1}{k^{u}}\right)=v_{p}\left(p\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\right)=v_{p}\left(p\right)+v_{p}\left(\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\right)$
$=1+v_{p}\left(\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\right)$.

Thus,

$v_{p}\left(\sum_{k=1}^{p-1}\frac{1}{k^{u}}\right)=1+v_{p}\left(\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\right)$.

Hence, instead of showing $v_{p}\left(\sum_{k=1}^{p-1}\frac{1}{k^{u}}\right)\geq 2$, it will be enough to prove $v_{p}\left(\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\right)\geq 1$. This is equivalent to $v_{p}\left(\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\right)>0$, i. e. to $\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\equiv 0\mod p$. Now we start working in $\mathbb{Z}_{p}$. In fact, we can consider all the fractions $\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}$ in $\mathbb{Z}_{p}$ since they have nonnegative p-adic evaluations (because their denominators, $k^{u}\left(p-k\right)^{u}$, are not divisible by p, since $1\leq k\leq p-1$ and p is a prime). The numerators $p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}$ of these fractions can be heavily simplified, namely to $uk^{u-1}$, since $p\equiv 0\mod p$, and thus all terms containing p can be omitted. Also, the denominators can be simplified: Since $p-k\equiv-k\mod p$, we have $k^{u}\left(p-k\right)^{u}\equiv k^{u}\left(-k\right)^{u}=\left(-1\right)^{u}k^{2u}$. Hence,

$\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\equiv\sum_{k=1}^{p-1}\frac{uk^{u-1}}{\left(-1\right)^{u}k^{2u}}\equiv\frac{u}{\left(-1\right)^{u}}\sum_{k=1}^{p-1}k^{-u-1}\mod p$.

But we are working in $\mathbb{Z}_{p}$, and thus, by Fermat's small theorem, $k^{p-1}\equiv 1\mod p$ for every integer k such that $1\leq k\leq p-1$. Thus, $k^{-u-1}\equiv k^{-u-1}k^{p-1}=k^{p-u-2}\mod p$, and this sum becomes

$\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\equiv\frac{u}{\left(-1\right)^{u}}\sum_{k=1}^{p-1}k^{p-u-2}\mod p$.

Now, $p-u-2\geq 1$ (since $p\geq u+3$) and $p-u-2\leq p-2$. Also, p is an odd prime (since p is a prime and p > 2). Now, according to http://www.problem-solving.be/pen/viewtopic.php?t=676 part [b]a)[/b] (and also http://www.mathlinks.ro/Forum/viewtopic.php?t=40171 ), we have:

[color=blue][b]Theorem 2.[/b] If p is an odd prime and $\rho$ is an integer such that $1\leq\rho\leq p-2$, then $p\mid\sum_{k=1}^{p-1}k^{\rho}$.[/color]

Applying this Theorem 2 to our prime p and $\rho=p-u-2$ (we know that p is an odd prime and $\rho=p-u-2$ satisfies $1\leq p-u-2\leq p-2$), we get $p\mid\sum_{k=1}^{p-1}k^{p-u-2}$, so that $\sum_{k=1}^{p-1}k^{p-u-2}\equiv 0\mod p$, and thus

$\sum_{k=1}^{p-1}\frac{p^{u-1}-up^{u-2}k\pm ...+uk^{u-1}}{k^{u}\left(p-k\right)^{u}}\equiv\frac{u}{\left(-1\right)^{u}}\sum_{k=1}^{p-1}k^{p-u-2}\equiv\frac{u}{\left(-1\right)^{u}}\cdot 0=0\mod p$.

This completes the proof of Theorem 1.

Darij

----------------------------------------------------------------------------------------------------------------------------

http://www.problem-solving.be/pen/viewtopic.php?t=34
Problem A 32

I don't like problems about primes abusing the letter $p$, so let's rename stuff:

[quote="Peter"]Let $a$ and $b$ be natural numbers such that $$\frac{a}{b}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots -\frac{1}{1318}+ \frac{1}{1319}.$$ Prove that $a$ is divisible by $1979$.[/quote]

I will assume paragraphs 1. and 2. of http://www.mathlinks.ro/Forum/viewtopic.php?t=150391 (or http://www.problem-solving.be/pen/viewtopic.php?t=25 ) post #4 as known.

Note that $1979$ is a prime (I am wondering whether the IMO contestants had to check that by hand or they were supposed to know that). We are going to prove $v_{1979}\left(\frac{a}{b}\right)\geq 1$, because this will yield $v_{1979}\left(a\right)=v_{1979}\left(\frac{a}{b}\cdot b\right)=\underbrace{v_{1979}\left(\frac{a}{b}\right)}_{\geq 1}+\underbrace{v_{1979}\left(b\right)}_{\geq 0\text{, since }b\text{ is an integer}}\geq 1$, so that $1979\mid a$, and thus the problem will be solved.

In order to prove that $v_{1979}\left(\frac{a}{b}\right)\geq 1$, we note that $\frac{a}{b}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots -\frac{1}{1318}+ \frac{1}{1319}=\sum_{i=1}^{\left\lfloor 2\cdot 1979/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i}$, so we have to show that $v_{1979}\left(\sum_{i=1}^{\left\lfloor 2\cdot 1979/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i}\right)\geq 1$. This is a particular case ($p=1979$) of the following theorem:

[color=blue][b]Theorem 1.[/b] Let $p$ be a prime such that $p>3$. Then, $v_p\left(\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i}\right)\geq 1$.[/color]

[i]Proof of Theorem 1.[/i] First we prove that

[color=green][b](1)[/b][/color] $p-\left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor = \left\lfloor 2p/3\right\rfloor +1$.

In fact, since $p$ is a prime and $p>3$, we have $3\nmid p$. Thus, either $p\equiv 1\mod 3$ or $p\equiv 2\mod 3$.

If $p\equiv 1\mod 3$, then $\frac{p-1}{3}\in\mathbb{Z}$, so that $\left\lfloor\frac{2p}{3}\right\rfloor = 2\cdot\frac{p-1}{3}$ (since $2\cdot\frac{p-1}{3}\in\mathbb{Z}$ (because $\frac{p-1}{3}\in\mathbb{Z}$) and $2\cdot\frac{p-1}{3}\leq\frac{2p}{3}<2\cdot\frac{p-1}{3}+1$) and therefore $\left\lfloor\left\lfloor\frac{2p}{3}\right\rfloor /2\right\rfloor = \frac{p-1}{3}$ (since $\left\lfloor\frac{2p}{3}\right\rfloor /2=\left(2\cdot\frac{p-1}{3}\right)/2=\frac{p-1}{3}$ and $\frac{p-1}{3}\in\mathbb{Z}$), so that

$p-\left\lfloor\left\lfloor\frac{2p}{3}\right\rfloor /2\right\rfloor =p-\frac{p-1}{3}=2\cdot\frac{p-1}{3}+1= \left\lfloor\frac{2p}{3}\right\rfloor +1$,

and therefore [color=green][b](1)[/b][/color] is proven for the case $p\equiv 1\mod 3$.

If $p\equiv 2\mod 3$, then $\frac{p-2}{3}\in\mathbb{Z}$, so that $\left\lfloor\frac{2p}{3}\right\rfloor = 2\cdot\frac{p-2}{3}+1$ (since $2\cdot\frac{p-2}{3}+1\in\mathbb{Z}$ (because $\frac{p-2}{3}\in\mathbb{Z}$) and $2\cdot\frac{p-2}{3}+1\leq\frac{2p}{3}<\left(2\cdot\frac{p-2}{3}+1\right)+1$) and therefore $\left\lfloor\left\lfloor\frac{2p}{3}\right\rfloor /2\right\rfloor = \frac{p-2}{3}$ (since $\left\lfloor\frac{2p}{3}\right\rfloor /2=\left(2\cdot\frac{p-2}{3}+1\right)/2=\frac{p-2}{3}+\frac{1}{2}$ and $\frac{p-2}{3}\in\mathbb{Z}$), so that

$p-\left\lfloor\left\lfloor\frac{2p}{3}\right\rfloor /2\right\rfloor =p-\frac{p-2}{3}=\left(2\cdot\frac{p-2}{3}+1\right)+1= \left\lfloor\frac{2p}{3}\right\rfloor +1$,

and therefore [color=green][b](1)[/b][/color] is proven for the case $p\equiv 2\mod 3$.

Hence, [color=green][b](1)[/b][/color] is proven in both possible cases, and we can step to the actual proof of Theorem 1.

We work with fractions modulo $p$, noting that we can divide by every $i\in\left\{1;\;2;\;...;\;p-1\right\}$ modulo $p$. Obviously,

$\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i}=\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is odd}}}\frac{\left(-1\right)^{i-1}}{i}+\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is even}}}\frac{\left(-1\right)^{i-1}}{i}$
$=\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is odd}}}\frac{1}{i}+\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is even}}}\frac{-1}{i}=\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is odd}}}\frac{1}{i}-\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is even}}}\frac{1}{i}$
$=\left(\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is odd}}}\frac{1}{i}+\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is even}}}\frac{1}{i}\right)-2\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is even}}}\frac{1}{i}=\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{1}{i}-2\sum_{\substack{1\leq i\leq \left\lfloor 2p/3\right\rfloor ;\\ i\text{ is even}}}\frac{1}{i}$
$=\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{1}{i}-2\sum_{j=1}^{\left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor}\frac{1}{2j}=\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{1}{i}+\sum_{j=1}^{\left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor}\frac{1}{-j}$.
$\equiv\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{1}{i}+\sum_{j=1}^{\left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor}\frac{1}{p-j}$
$=\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{1}{i}+\sum_{i=p-\left\lfloor \left\lfloor 2p/3\right\rfloor /2\right\rfloor}^{p-1}\frac{1}{i}$      (here we substituted $j$ by $p-i$ in the second sum)
$=\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{1}{i}+\sum_{i=\left\lfloor 2p/3\right\rfloor+1}^{p-1}\frac{1}{i}$      (by [color=green][b](1)[/b][/color])
$=\sum_{i=1}^{p-1}\frac{1}{i}\mod p$.

Now, $\sum_{i=1}^{p-1}\frac{1}{i}\equiv 0\mod p$, as can be shown in different ways - e. g. as follows:

$\sum_{i=1}^{p-1}\frac{1}{i}=\frac12\cdot\left(\sum_{i=1}^{p-1}\frac{1}{i}+\sum_{i=1}^{p-1}\frac{1}{i}\right)$
$=\frac12\cdot\left(\sum_{i=1}^{p-1}\frac{1}{i}+\sum_{i=1}^{p-1}\frac{1}{p-i}\right)$             (here we substituted $i$ by $p-i$ in the second sum)
$=\frac12\cdot\sum_{i=1}^{p-1}\left(\frac{1}{i}+\frac{1}{p-i}\right)\equiv\frac12\cdot\sum_{i=1}^{p-1}\left(\frac{1}{i}+\frac{1}{-i}\right)=\frac12\cdot\sum_{i=1}^{p-1}0 = 0\mod p$;

hereby, we were allowed to divide by $2$ because $2\not\equiv 0\mod p$ (since $p>3$). Thus,

$\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i} \equiv \sum_{i=1}^{p-1}\frac{1}{i} \equiv 0\mod p$,

so that $v_p\left(\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i}\right)\geq 1$, and Theorem 1 is proven.

Darij

----------------------------------------------------------------------------------------------------------------------------

http://www.problem-solving.be/pen/viewtopic.php?t=26
Problem A 24

[quote="Peter"]Let $p>3$ is a prime number and $k=\lfloor\frac{2p}{3}\rfloor$. Prove that $${p \choose 1}+{p \choose 2}+\cdots +{p \choose k}$$ is divisible by $p^2$.[/quote]

I will assume paragraphs 1. and 2. of http://www.mathlinks.ro/Forum/viewtopic.php?t=150391 (or http://www.problem-solving.be/pen/viewtopic.php?t=25 ) post #4 as known.

We have to prove that $p^2\mid\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\binom{p}{i}$.

In http://www.mathlinks.ro/Forum/viewtopic.php?t=150400 (or http://www.problem-solving.be/pen/viewtopic.php?t=34 ) post #2, Theorem 1, I showed that $v_p\left(\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i}\right)\geq 1$. This rewrites as $\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{\left(-1\right)^{i-1}}{i} \equiv 0\mod p$, where we are working with fractions modulo $p$ (what is allowed in our case because the denominators are integers $i$ satisfying $1\leq i\leq\left\lfloor 2p/3\right\rfloor$, and these integers are not divisible by $p$). In other words, $\sum_{i=1}^{\left\lfloor 2p/3\right\rfloor}\frac{1}{i}\left(-1\right)^{i-1}\equiv 0\mod p$.

Now we prove a simple lemma:

[color=blue][b]Lemma 1.[/b] If $p$ is a prime and $i$ is an integer satisfying $0\leq i\leq p-1$, then $\binom{p-1}{i}\equiv\left(-1\right)^i\mod p$.[/color]

[i]Proof of Lemma 1.[/i] We have $\binom{p-1}{i}=\frac{\left(p-1\right)\cdot\left(p-2\right)\cdot ...\cdot\left(p-i\right)}{i!}$, and thus

$i!\cdot\binom{p-1}{i}=\left(p-1\right)\cdot\left(p-2\right)\cdot ...\cdot\left(p-i\right)\equiv\left(-1\right)\cdot\left(-2\right)\cdot ...\cdot\left(-i\right)$
$=\left(-1\right)^i\cdot\left(1\cdot 2\cdot ...\cdot i\right)=\left(-1\right)^i\cdot i!\mod p$.

Now, $i!$ is coprime with $p$ (since $i!=1\cdot 2\cdot ...\cdot i$, and all the numbers $1$, $2$, ..., $i$ are coprime with $p$ since $p$ is a prime and $i0$ only. In this case, $k!$ is coprime with $p$ (since $k!=1\cdot 2\cdot ...\cdot k$, and all numbers $1$, $2$, ..., $k$ are coprime with $p$, since $p$ is a prime and $ku$, since $p^2=u^2+2v^2>u^2$ what is because $v$ is positive.

The prime $p$ is odd. This is because else we would have $p=2$, so that $4=2^2=p^2=u^2+2v^2$, and thus $4\geq 2v^2$, so that $2\geq v^2$, and thus $v\leq\sqrt2$, so that $v=1$ (since $v$ is a positive integer, and the only positive integer $\leq\sqrt2$ is $1$), so that $4=u^2+2v^2=u^2+2\cdot 1^2=u^2+2$ yields $2=u^2$, what is impossible since $u$ is an integer and $2$ is not a square.

Since $p$ is odd, $p^2$ must also be odd. Since $p^2=u^2+2v^2$, this yields that $u^2+2v^2$ is odd, so that $u^2$ is odd, so that $u$ is odd. Thus, $u\neq 0$. Since we know that $u$ is nonnegative, it hence follows that $u$ is positive. We also know that $v$ is positive.

Assume that the two integers $\frac{p-u}{2}$ and $\frac{p+u}{2}$ have a common prime divisor $q$. Then, $q$ also divides $\frac{p-u}{2}+\frac{p+u}{2}=p$. Thus, $q$ is a prime divisor of $p$. Since $p$ is a prime, and thus the only prime divisor of $p$ is $p$ itself, this yields $q=p$. Hence, $p$ is a common prime divisor of $\frac{p-u}{2}$ and $\frac{p+u}{2}$. Therefore, $p$ also divides $\frac{p+u}{2}-\frac{p-u}{2}=u$. Since $u$ is positive, this yields $u\geq p$. This contradicts with $p>u$. Hence, our assumption that the two integers $\frac{p-u}{2}$ and $\frac{p+u}{2}$ have a common prime divisor was wrong. Hence, the two integers $\frac{p-u}{2}$ and $\frac{p+u}{2}$ are coprime.

Now, we divide the equation $\left(p-u\right)\left(p+u\right)=2v^2$ by $4$ and obtain $\frac{p-u}{2}\cdot\frac{p+u}{2}=\frac{v^2}{2}$. Since $\frac{p-u}{2}$ and $\frac{p+u}{2}$ are integers, this yields that $\frac{v^2}{2}$ is an integer, so that $v^2$ is even, so that $v$ is even, and thus $v=2V$ for some integer $V$. Since $v$ is positive, it follows that $V$ is positive as well.

Thus, $\frac{p-u}{2}\cdot\frac{p+u}{2}=\frac{v^2}{2}=\frac{\left(2V\right)^2}{2}=2V^2$. Hence, $2\mid\frac{p-u}{2}\cdot\frac{p+u}{2}$. Since $2$ is a prime, it thus follows that $2$ divides at least one of the numbers $\frac{p-u}{2}$ and $\frac{p+u}{2}$. We will only deal with the case when $2$ divides $\frac{p-u}{2}$; the case when $2$ divides $\frac{p+u}{2}$ is analogous and left to the reader.

Since $2$ divides $\frac{p-u}{2}$, the number $\frac{p-u}{2}/2=\frac{p-u}{4}$ is an integer; besides, it is positive (since $p>u$). Now, dividing the equation $\frac{p-u}{2}\cdot\frac{p+u}{2}=2V^2$ by $2$, we get $\frac{p-u}{4}\cdot\frac{p+u}{2}=V^2$.

Now, $\frac{p-u}{4}$ and $\frac{p+u}{2}$ are two coprime positive integers (in fact, we know that they are positive integers, and they are coprime because $\frac{p-u}{2}$ and $\frac{p+u}{2}$ are coprime). Since $\frac{p-u}{4}\cdot\frac{p+u}{2}=V^2$ is the $2$-nd power of a positive integer, Lemma 1 thus yields that both $\frac{p-u}{4}$ and $\frac{p+u}{2}$ are $2$-nd powers of positive integers. Hence, there exist positive integers $\lambda$ and $\mu$ such that $\frac{p-u}{4}=\lambda^2$ and $\frac{p+u}{2}=\mu^2$.

Thus, $p=\frac{p+u}{2}+2\cdot\frac{p-u}{4}=\mu^2+2\lambda^2$. Since $\lambda\neq 0$ (because $\lambda$ is positive), this yields $p\in A$, and the problem is solved.

Darij

----------------------------------------------------------------------------------------------------------------------------

http://www.problem-solving.be/pen/viewtopic.php?t=337
Problem I 2

[quote="Peter"]Prove that for any positive integer $n$, $$\left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{n+2}{6} \right\rfloor + \left\lfloor \frac{n+4}{6} \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n+3}{6} \right\rfloor .$$[/quote]

A solution for every [b]real[/b] $n$, not just for positive integers $n$:

[color=blue][b]Theorem 1.[/b] Let $x$ be a real and $n$ a positive integer. Then,

[/color][color=green][b](1)[/b][/color][color=blue] $\sum_{k=0}^{n-1}\left\lfloor x+\frac{k}{n}\right\rfloor = \left\lfloor nx\right\rfloor$.[/color]

Here comes a somewhat nonstandard [i]proof of Theorem 1.[/i] We first note that it is enough to prove the equality [color=green][b](1)[/b][/color] for all [b]nonnegative[/b] reals $x$. This is because, once this equality is proven for all nonnegative reals $x$, we can conclude that it holds for all reals $x$ as follows:

For any real $y$, there exists an integer $s$ such that $y+s$ is nonnegative (just take $s$ big enough); therefore, since the formula [color=green][b](1)[/b][/color] holds for nonnegative $x$, we can apply it to $x=y+s$ and get

[color=green][b](2)[/b][/color] $\sum_{k=0}^{n-1}\left\lfloor \left(y+s\right)+\frac{k}{n}\right\rfloor = \left\lfloor n\left(y+s\right)\right\rfloor$;

but since $s$ is an integer,

$\sum_{k=0}^{n-1}\left\lfloor \left(y+s\right)+\frac{k}{n}\right\rfloor = \sum_{k=0}^{n-1}\left\lfloor y+\frac{k}{n}+s\right\rfloor = \sum_{k=0}^{n-1}\left(\left\lfloor y+\frac{k}{n}\right\rfloor+s\right)$
$= \left(\sum_{k=0}^{n-1}\left\lfloor y+\frac{k}{n}\right\rfloor\right)+sn$

and

$\left\lfloor n\left(y+s\right)\right\rfloor = \left\lfloor ny+sn\right\rfloor = \left\lfloor ny\right\rfloor +sn$,

so that [color=green][b](2)[/b][/color] becomes

$\left(\sum_{k=0}^{n-1}\left\lfloor y+\frac{k}{n}\right\rfloor\right)+sn = \left\lfloor ny\right\rfloor +sn$,

thus

$\sum_{k=0}^{n-1}\left\lfloor y+\frac{k}{n}\right\rfloor = \left\lfloor ny\right\rfloor$,

and therefore [color=green][b](1)[/b][/color] holds for $x=y$; hence, [color=green][b](1)[/b][/color] is proven for all reals $x$.

Thus, it is enough to prove [color=green][b](1)[/b][/color] for all nonnegative reals $x$ only. So we will assume that $x$ is nonnegative from now on.

[color=green][b](3)[/b][/color] $\left\lfloor u\right\rfloor = \sum_{i\in\mathbb{N}}\left[ i\leq u\right]$

for every nonnegative real $u$.

Time for the actual idea of the proof:

$\sum_{k=0}^{n-1}\left\lfloor x+\frac{k}{n}\right\rfloor = \sum_{k=0}^{n-1}\sum_{i\in\mathbb{N}}\left[ i\leq x+\frac{k}{n}\right]$        (after [color=green][b](3)[/b][/color], since $x+\frac{k}{n}$ is nonnegative)
$= \sum_{k=0}^{n-1}\sum_{i\in\mathbb{N}}\left[ in\leq nx+k\right] = \sum_{k=0}^{n-1}\sum_{i\in\mathbb{N}}\left[ in-k\leq nx\right]$
$= \sum_{k=0}^{n-1}\sum_{j\in\mathbb{N};\ j\equiv -k\text{ mod } n}\left[ j\leq nx\right]$         (since $\left\{in-k\mid i\in\mathbb{N}\right\}=\left\{j\mid j\in\mathbb{N}\and j\equiv -k\text{ mod } n\right\}$)
$= \sum_{j\in\mathbb{N}}\left[ j\leq nx\right] = \left\lfloor nx\right\rfloor$      (after [color=green][b](3)[/b][/color], since $nx$ is nonnegative).

Thus, we have proven [color=green][b](1)[/b][/color] - at least, for nonnegative $x$, but as we know this is enough to be sure that [color=green][b](1)[/b][/color] holds for all real $x$. Thus, Theorem 1 is proven.

Now, on to solving the original problem: Theorem 1 yields

$\left\lfloor \frac{n}{6} \right\rfloor + \left\lfloor \frac{n}{6}+\frac13 \right\rfloor + \left\lfloor \frac{n}{6}+\frac23 \right\rfloor = \left\lfloor 3\frac{n}{6} \right\rfloor$,

what rewrites as

$\left\lfloor \frac{n}{6} \right\rfloor + \left\lfloor \frac{n+2}{6} \right\rfloor + \left\lfloor \frac{n+4}{6} \right\rfloor = \left\lfloor \frac{n}{2} \right\rfloor$,

as well as

$\left\lfloor \frac{n}{6} \right\rfloor + \left\lfloor \frac{n}{6}+\frac12 \right\rfloor = \left\lfloor 2\frac{n}{6} \right\rfloor$,

what rewrites as

$\left\lfloor \frac{n}{6} \right\rfloor + \left\lfloor \frac{n+3}{6} \right\rfloor = \left\lfloor \frac{n}{3} \right\rfloor$.

Thus,

$\left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{n+2}{6} \right\rfloor + \left\lfloor \frac{n+4}{6} \right\rfloor = \left( \left\lfloor \frac{n}{3} \right\rfloor - \left\lfloor \frac{n}{6} \right\rfloor \right) + \left( \left\lfloor \frac{n}{6} \right\rfloor + \left\lfloor \frac{n+2}{6} \right\rfloor + \left\lfloor \frac{n+4}{6} \right\rfloor \right)$
$= \left( \left\lfloor \frac{n}{3} \right\rfloor - \left\lfloor \frac{n}{6} \right\rfloor \right) + \left\lfloor \frac{n}{2} \right\rfloor = \left( \left\lfloor \frac{n}{2} \right\rfloor - \left\lfloor \frac{n}{6} \right\rfloor \right) + \left\lfloor \frac{n}{3} \right\rfloor$
$= \left( \left\lfloor \frac{n}{2} \right\rfloor - \left\lfloor \frac{n}{6} \right\rfloor \right) + \left( \left\lfloor \frac{n}{6} \right\rfloor + \left\lfloor \frac{n+3}{6} \right\rfloor \right) = \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n+3}{6} \right\rfloor$,

and the problem is solved.

Darij

----------------------------------------------------------------------------------------------------------------------------

http://problem-solving.be/pen/viewtopic.php?t=448
Problem M 23

[quote="Peter"]Define $$\begin{cases}d(n, 0)=d(n, n)=1&(n \ge 0),\\ md(n, m)=md(n-1, m)+(2n-m)d(n-1,m-1)&(00). Thus, in all three cases, we get d\left(n,m\right)=\binom{n}{m}^2, so that [color=green][b](2)[/b][/color] holds for our two integers n and m. Hence, the induction step is complete, and [color=green][b](2)[/b][/color] is proven. As said above, this solves the problem. Darij ---------------------------------------------------------------------------------------------------------------------------- http://problem-solving.be/pen/viewtopic.php?t=454 http://www.mathlinks.ro/Forum/viewtopic.php?t=150820 Problem M 29 [quote="Peter"]The sequence \{a_{n}\}_{n \ge 1} is defined by a_{1}=1 and$$ a_{n+1} = \frac{a_{n}}{2}+ \frac{1}{4a_{n}} \; (n \in \mathbb{N}). $$Prove that \sqrt{\frac{2}{2a_{n}^2 -1}} is a positive integer for n>1.[/quote] I find such problems beautiful, but unfortunately their solutions use to consist mostly of computation... First, it is clear by induction that a_{n}\in\mathbb{Q} and a_{n}>0 for every n\in\mathbb{N}. Hence, for every n\in\mathbb{N}, we have \frac{a_{n}}{2}\neq\frac{1}{4a_{n}} (in fact, \frac{a_{n}}{2}=\frac{1}{4a_{n}} would lead to a_{n}^{2}=\frac{1}{2}, but this is impossible since a_{n}\in\mathbb{Q}, and \frac{1}{2} is not a square of a rational number), so that \frac{a_{n}}{2}-\frac{1}{4a_{n}}\neq0 and thus [color=green][b](1)[/b][/color] \left( \frac{a_{n}}{2}-\frac{1}{4a_{n}}\right) ^{2}>0 for every n\in\mathbb{N}. Further, [color=green][b](2)[/b][/color] 2a_{n}^{2}-1>0 for every n\in\mathbb{N}. In fact, for n=1, this is clear since 2a_{1}^{2}-1=2\cdot1^{2}-1=1>0, and for n>1, this follows from 2a_{n}^{2}-1=2\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right)^{2}-1=2\left( \frac{a_{n-1}}{2}-\frac{1}{4a_{n-1}}\right) ^{2}>0 (the last step used \left( \frac{a_{n-1}}{2}-\frac{1}{4a_{n-1}}\right)^{2}>0, what follows from [color=green][b](1)[/b][/color]). Now, set b_{n}=\sqrt{\frac{2}{2a_{n}^{2}-1}} for every n\in\mathbb{N}. Note that b_{n} is well-defined since \frac{2}{2a_{n}^{2}-1}>0 (what is because 2a_{n}^{2}-1>0, as proven in [color=green][b](2)[/b][/color]). The crux of the solution is to prove that [color=green][b](3)[/b][/color] b_{n+1}=2b_{n}\left( 1+b_{n-1}^{2}\right)  for every integer n>1. Before we show this, we need two more lemmata. First, we prove that [color=green][b](4)[/b][/color] b_{n+1}=\frac{4a_{n}}{2a_{n}^{2}-1} for every n\in\mathbb{N}. In fact, b_{n+1}=\sqrt{\frac{2}{2a_{n+1}^{2}-1}}=\sqrt{\frac{2}{2\left(\frac{a_{n}}{2}+\frac{1}{4a_{n}}\right) ^{2}-1}}=\sqrt{\frac{2}{2\left(\frac{a_{n}}{2}-\frac{1}{4a_{n}}\right) ^{2}}} =\sqrt{\frac{1}{\left( \frac{a_{n}}{2}-\frac{1}{4a_{n}}\right) ^{2}}}=\frac{1}{\left\vert \frac{a_{n}}{2}-\frac{1}{4a_{n}}\right\vert }=\frac{1}{\left\vert \frac{2a_{n}^{2}-1}{4a_{n}}\right\vert }=\frac{4\left\vert a_{n}\right\vert }{\left\vert 2a_{n}^{2}-1\right\vert }, and since a_{n}>0 and 2a_{n}^{2}-1>0 (the latter according to [color=green][b](2)[/b][/color]), we have \left\vert a_{n}\right\vert =a_{n} and \left\vert 2a_{n}^{2}-1\right\vert =2a_{n}^{2}-1 and thus b_{n+1}=\frac{4\left\vert a_{n}\right\vert }{\left\vert 2a_{n}^{2}-1\right\vert }=\frac{4a_{n}}{2a_{n}^{2}-1}, so that [color=green][b](4)[/b][/color] is proven. Now we show that [color=green][b](5)[/b][/color] b_{n+1}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right) }{\left( 2a_{n-1}^{2}-1\right) ^{2}} for every integer n>1. In fact, [color=green][b](4)[/b][/color] yields b_{n+1}=\frac{4a_{n}}{2a_{n}^{2}-1}=\frac{4\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right) }{2\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right) ^{2}-1}=\frac{4\left( \frac{a_{n-1}}{2}+\frac{1}{4a_{n-1}}\right) }{2\left( \frac{a_{n-1}}{2}-\frac{1}{4a_{n-1}}\right) ^{2}} =\frac{4\frac{2a_{n-1}^{2}+1}{4a_{n-1}}}{2\left( \frac{2a_{n-1}^{2} -1}{4a_{n-1}}\right) ^{2}}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right)}{\left( 2a_{n-1}^{2}-1\right) ^{2}}. Now, let n>1 be an integer. Then, - [color=green][b](4)[/b][/color] yields b__{n}=\frac{4a_{n-1}}{2a_{n-1}^{2}-1} (since n-1\in\mathbb{N}); - [color=green][b](5)[/b][/color] yields b__{n+1}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right) }{\left( 2a_{n-1}^{2}-1\right) ^{2}}; - the definition of b_{n-1}, namely b_{n--1}=\sqrt{\frac{2}{2a_{n-1}^{2}-1}}, yields b_{n-1}^{2}=\frac{2}{2a_{n-1}^{2}-1}. Hence, 2b_{n}\left( 1+b_{n-1}^{2}\right) =2\cdot\frac{4a_{n-1}}{2a_{n-1}^{2}-1}\cdot\left( 1+\frac{2}{2a_{n-1}^{2}-1}\right)  =\frac{8a_{n-1}}{2a_{n-1}^{2}-1}\cdot\frac{2a_{n-1}^{2}+1}{2a_{n-1}^{2}-1}=\frac{8a_{n-1}\left( 2a_{n-1}^{2}+1\right) }{\left( 2a_{n-1}^{2}-1\right) ^{2}}=b_{n+1}, so that [color=green][b](3)[/b][/color] is proven. The rest is obvious: First, a_{1}=1 yields b_{1}=\sqrt{\frac{2}{2a_{1}^{2}-1}}=\sqrt{\frac{2}{2\cdot1^{2}-1}}=\sqrt{2}, so that b_{1}^{2}=2. Then, application of [color=green][b](4)[/b][/color] to n=1 yields b_{2}=\frac{4a_{1}}{2a_{1}^{2}-1}=\frac{4\cdot1}{2\cdot1^{2}-1}=4. Besides, application of [color=green][b](3)[/b][/color] to n=2 yields b_{3}=2b_{2}\left( 1+b_{1}^{2}\right) =2\cdot4\cdot\left( 1+2\right) =24. Thus, b_{2}=4 and b_{3}=24 are positive integers. Using the recursive equation [color=green][b](3)[/b][/color] for the sequence \left( b_{i}\right) _{i>1}, it thus follows by induction that b_{n} is a positive integer for every integer n>1. Since b_{n}=\sqrt{\frac{2}{2a_{n}^{2}-1}}, this means that \sqrt{\frac{2}{2a_{n}^{2}-1}} is a positive integer for every integer n>1. Problem solved. ---------------------------------------------------------------------------------------------------------------------------- http://problem-solving.be/pen/viewtopic.php?t=452 http://www.mathlinks.ro/Forum/viewtopic.php?t=150818 Problem M 27 [quote="Peter"]Let p \ge 3 be a prime number. The sequence \{a_{n}\}_{n \ge 0} is defined by a_{n}=n for all 0 \le n \le p-1, and a_{n}=a_{n-1}+a_{n-p} for all n \ge p. Compute a_{p^3} \; \pmod{p}.[/quote] I'm wondering... what makes this problem appear here and not in the L(inear Recurrences) section of PEN? Besides: Is it really a Canada 1986 problem? I can't find it at http://www.math.ca/Competitions/CMO/examt/english86.html or on Kalva. Now, for the solution: I claim that a_{p^3}\equiv -1\text{ mod }p. The proof requires some basics of what is known as [i]umbral calculus[/i] - computing with operators on sequences. Besides, I will use linear algebra to an extent which should be known to IMO participants. I will first introduce the part of umbral calculus I will need: A [i]bisequence[/i] in a set K will mean a mapping from the set \mathbb{Z} to the set K. For any set K, we denote by K^{\mathbb{Z}} the set of all bisequences in K. Roughly speaking, a bisequence is like a sequence, but its terms are labeled by integers and not by natural numbers. We define a mapping S:K^{\mathbb{Z}}\to K^{\mathbb{Z}} such that, if u\in K^{\mathbb{Z}} is a mapping from the set \mathbb{Z} to the set K, then Su is the mapping from the set \mathbb{Z} to the set K defined by \left(Su\right)\left(x\right)=u\left(x-1\right) for every x\in\mathbb{Z}. Note that we write Su for S\left(u\right). Roughly speaking, the mapping S shifts every bisequence one term forward. This mapping S is actually called the [i]shift operator[/i]. By induction, it can be seen that \left(S^k u\right)\left(x\right)=u\left(x-k\right) for every k\in\mathbb{Z} and every x\in\mathbb{Z}. If K is a field, then K^{\mathbb{Z}} can be naturally considered as an (infinite-dimensional) vector space over K as follows: - the zero vector is the "zero bisequence"$$0\in K^{\mathbb{Z}}$defined by$0\left(x\right)=0$for every$x\in\mathbb{Z}$; - for any two elements$a$and$b$of$K^{\mmathbb{Z}}$, we define the element$a+b$of$K^{\mathbb{Z}}$by setting$\left(a+b\right)\left(x\right)=a\left(x\right)+b\left(x\right)$for every$x\in\mathbb{Z}$; - for any element$a$of$K^{\mathbb{Z}}$annd any element$\lambda$of$K$, we define the element$\lambda a$of$K^{\mathbb{Z}}$by setting$\left(\lambda a\right)\left(x\right)=\lambda\cdot a\left(x\right)$for every$x\in\mathbb{Z}$. It is easily seen that (if$K$is a field) the transformation$S$is linear, i. e. it is an endomorphism of this vector space$K^{\mathbb{Z}}$. Note that all endomorphisms of the vector space$K^{\mathbb{Z}}$form a skew ring; its addition is pointwise addition, its multiplication is composition of endomorphisms; its additive unit is the zero endomorphism (this is the endomorphism sending everything to the zero vector); its multiplicative unit is the identity endomorphism. Now we show a basic fact from algebra, but first a matter of notation: I call a [i]skew ring[/i] what most other people just call "ring with$1$" (i. e. a set with an Abelian additive group structure, an associative multiplication with a unit, and distributivity). I, personally, use the word "ring" for commutative skew rings. Two elements$a$and$b$of a skew ring are said to [i]commute[/i] if$ab=ba$. [color=blue][b]Lemma 1.[/b] Let$p$be a prime number, and let$R$be a skew ring such that$p=0$in$R$(hereby,$p$means$\underbrace{1+1+...+1}_{p\text{ ones}}$, and$0$and$1$mean the additive and multiplicative units of$R$). If$a$and$b$are two elements of$R$which commute, then$\left(a+b\right)^p=a^p+b^p$.[/color] [i]Proof of Lemma 1.[/i] Since the elements$a$and$b$commute, we can apply the binomial theorem to them, and we obtain$\left(a+b\right)^p=\sum_{k=0}^p\binom{p}{k}a^kb^{p-k}=a^p+\sum_{k=1}^{p-1}\binom{p}{k}a^kb^{p-k}+b^p$. Now, it is known from number theory that$\binom{p}{k}$is divisible by$p$for each$k\in\left\{1,2,...,p-1\right\}$(since$p$is prime), so that in$R$we have$\binom{p}{k}=0$(because$p=0$). Hence, we obtain$\left(a+b\right)^p=a^p+\sum_{k=1}^{p-1}\binom{p}{k}a^kb^{p-k}+b^p=a^p+\sum_{k=1}^{p-1}0a^kb^{p-k}+b^p=a^p+b^p$, and Lemma 1 is proven. Now we can show: [color=blue][b]Lemma 2.[/b] Let$p$be a prime number with$p\geq 3$, and let$R$be a skew ring such that$p=0$in$R$. Let$x$be an element of$R$. Then, there exists an element$t\in R$such that$x^{p^2-1}-1=t\left(x^p+x-1\right)$.[/color] [i]Proof of Lemma 2.[/i] First, since$p=0$in$R$, we can apply Lemma 1 to any two commuting elements of$R$. Besides,$p$is odd (since$p$is a prime and is$\geq 3$), so that$\left(-x\right)^p=-x^p$. Now, since the values of any two polynomials of$x$with integer coefficients commute with each other, we can compute:$xx^{p^{2}-1}=x^{p^{2}}=\left(  x^{p}\right)  ^{p}=\left(  \left( x^{p}+x-1\right)  +\left(  1+\left(  -x\right)  \right)  \right)  ^{p}=\left(  x^{p}+x-1\right)  ^{p}+\left(  1+\left(  -x\right)  \right)  ^{p}$(by Lemma 1, applied to the commuting elements$x^{p}+x-1$and$1+\left(-x\right)$of$R$)$=\left(  x^{p}+x-1\right)  ^{p}+\left(  1^{p}+\left(  -x\right)  ^{p}\right) $(since$\left(  1+\left(  -x\right)  \right)  ^{p} = 1^{p}+\left(  -x\right)  ^{p}$by Lemma 1, applied to the commuting elements$1$and$-x$of$R$)$=\left(  x^{p}+x-1\right)  ^{p}+\left(  1+\left(  -x\right)  ^{p}\right) =\left(  x^{p}+x-1\right)  ^{p}+\left(  1-x^{p}\right)  $(since$\left( -x\right)  ^{p}=-x^{p}$)$=\left(  x^{p}+x-1\right)  ^{p}-\left(  x^{p}+x-1\right)  +x=\left(  x^{p}+x-1\right)  \left(  \left(  x^{p}+x-1\right)  ^{p-1}-1\right) +x$, so that$x\left(  x^{p^{2}-1}-1\right)  =xx^{p^{2}-1}-x=\left(  \left(  x^{p}+x-1\right)  \left(  \left(  x^{p}+x-1\right) ^{p-1}-1\right)  +x\right)  -x=\left(  x^{p}+x-1\right)  \left(  \left(  x^{p}+x-1\right)  ^{p-1}-1\right) $. Consequently,$x^{p^{2}-1}-1=\left( x^{p}+x\right) \left( x^{p^{2}-1}-1\right) -\left( x^{p}+x-1\right) \left( x^{p^{2}-1}-1\right) =\left( x^{p-1}+1\right) x\left( x^{p^{2}-1}-1\right) -\left( x^{p}+x-1\right) \left( x^{p^{2}-1}-1\right) =\left( x^{p-1}+1\right) \left( x^{p}+x-1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) -\left( x^{p}+x-1\right) \left( x^{p^{2}-1}-1\right) =\left( x^{p}+x-1\right) \left( \left( x^{p-1}+1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) -\left( x^{p^{2}-1}-1\right) \right) =\left( \left( x^{p-1}+1\right) \left( \left( x^{p}+x-1\right) ^{p-1}-1\right) -\left( x^{p^{2}-1}-1\right) \right) \left( x^{p}+x-1\right) $, and setting$t=\left( x^{p-1}+1\right) \left( \left( x^{p}+x-1\right)^{p-1}-1\right) - \left( x^{p^{2}-1}-1\right) $, we get$x^{p^{2}-1}-1=t\left( x^{p}+x-1\right) $, so that Lemma 2 is proven. Now, to the solution of the problem: We define a bisequence$u\in\mathbb{Z}^{\mathbb{Z}}$recurrently by setting$u\left(n\right)=n$for all integers$n$such that$0\leq n\leq p-1$and the recursion$u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$for all$n\in\mathbb{Z}$. Note that this recursion has to be applied "forwards" (i. e. in the form$u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$) in order to compute the terms$u\left(p\right)$,$u\left(p+1\right)$,$u\left(p+2\right)$, ..., and applied "backwards" (i. e. in the form$u\left(n-p\right)=u\left(n\right)-u\left(n-1\right)$) in order to compute the terms$u\left(-1\right)$,$u\left(-2\right)$,$u\left(-3\right)$, .... The sequences$\left(u\left(0\right),u\left(1\right),u\left(2\right),...\right)$and$\left(a_0,a_1,a_2,...\right)$are equal, because they have the same$p$starting values ($a_n=n$and$u\left(n\right)=n$for all integers$n$such that$0\leq n\leq p-1$) and satisfy the same$p+1$-term recursion ($a_{n}=a_{n-1}+a_{n-p}$and$u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$). In other words,$u\left(n\right)=a_n$for every integer$n\geq 0$. Next, we define a bisequence$\overline{u}\in\left(\mathbb{F}_p\right)^{\mathbb{Z}}$as follows: For every integer$n$, let$\overline{u}\left(n\right)$be the residue class of$u\left(n\right)$modulo$p$. Then, since$u\left(n\right)=u\left(n-1\right)+u\left(n-p\right)$for every$n\in\mathbb{Z}$, we have$\overline{u}\left(n\right)=\overline{u}\left(n-1\right)+\overline{u}\left(n-p\right)$for every$n\in\mathbb{Z}$. Since$\overline{u}\left(n-1\right)=\left(S\overline{u}\right)\left(n\right)$and$\overline{u}\left(n-p\right)=\left(S^p\overline{u}\right)\left(n\right)$, this becomes$\overline{u}\left(n\right)=\left(S\overline{u}\right)\left(n\right)+\left(S^p\overline{u}\right)\left(n\right)$for every$n\in\mathbb{Z}$. Hence,$\overline{u}=S\overline{u}+S^p\overline{u}$, so that$\left(S^p+S-1\right)\overline{u}=0$(hereby,$1$stands for the identity endomorphism of$\left(\mathbb{F}_p\right)^{\mathbb{Z}}$; in fact, we can call it$1$because it is the multiplicative unit of the skew ring of endomorphisms of$\left(\mathbb{F}_p\right)^{\mathbb{Z}}$). The skew ring of endomorphisms of the vector space$\left(\mathbb{F}_p\right)^{\mathbb{Z}}$satisfies$p=0$(since$p=0$holds in$\mathbb{F}_p$). Thus, applying Lemma 2 to the element$x=S$of this skew ring, we see that there exists an element$T$of this skew ring such that$S^{p^2-1}-1=T\left(S^p+S-1\right)$. Hence,$S^{p^3-p}-1=\left(S^{p^2-1}\right)^p-1=\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot \left(S^{p^2-1}-1\right)=\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot T\left(S^p+S-1\right)$. Thus,$\left(S^{p^3-p}-1\right)\overline{u}=\left(\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot T\left(S^p+S-1\right)\right)\overline{u}=\sum_{k=0}^{p-1}\left(S^{p^2-1}\right)^k\cdot T\cdot\underbrace{\left(S^p+S-1\right)\right)\overline{u}\right)}_{=0}=0$, so that$S^{p^3-p}\overline{u}=1\overline{u}$. This yields that$\left(S^{p^3-p}\overline{u}\right)\left(n\right)=\left(1\overline{u}\right)\left(n\right)$for every$n\in\mathbb{Z}$. In other words,$\overline{u}\left(n-\left(p^3-p\right)\right)=\overline{u}\left(n\right)$for every$n\in\mathbb{Z}$. Applying this to$n=p^3$, we get$\overline{u}\left(p^3-\left(p^3-p\right)\right)=\overline{u}\left(p^3\right)$. In other words,$\overline{u}\left(p\right)=\overline{u}\left(p^3\right)$. Since$\overline{u}\left(n\right)$was defined as the residue class of$u\left(n\right)$modulo$p$, this equation yields that$u\left(p\right)\equiv u\left(p^3\right)\text{ mod }p$. Since$u\left(n\right)=a_n$for all integers$n\geq 0$, this rewrites as$a_p\equiv a_{p^3}\text{ mod }p$. Now, applying the recursion$a_{n}=a_{n-1}+a_{n-p}$to$n=p$, we get$a_p=a_{p-1}+a_{p-p}=a_{p-1}+a_0=\left(p-1\right)+0=p-1$. Thus,$a_p\equiv a_{p^3}\text{ mod }p$yields$p-1\equiv a_{p^3}\text{ mod }p$, so that$a_{p^3}\equiv p-1\equiv -1\text{ mod }p$. This completes the proof. [b]PS.[/b] In the above, I showed that$a_{p^3}\equiv -1\text{ mod }p$for every prime$p\geq 3$. By inspection you can see that this also holds for$p=2$. Darij ---------------------------------------------------------------------------------------------------------------------------- http://www.mathlinks.ro/Forum/viewtopic.php?t=150391 NEW VERSION Problem A 23 [quote="Peter"](Wolstenholme's Theorem) Prove that if $1 + \frac {1}{2} + \frac {1}{3} + \cdots + \frac {1}{p - 1}$ is expressed as a fraction, where$p \ge 5$is a prime, then$p^{2}$divides the numerator.[/quote] This is a slightly edited version of [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=46121]an older MathLinks post of mine[/url], and I am submitting it here since I will refer to it in a number of other proofs. I will generalize the problem, but first I explain some preliminaries about primes. [color=blue][b]1. p-adic evaluation[/b][/color] Let p be an arbitrary prime. We denote by$\mathbb{Z}_{p}$the field of residues of integers modulo p. For any rational number x, we will now define a so-called [i]p-adic evaluation of x[/i]. This evaluation will be denoted by$v_{p}\left(x\right)$, and it is defined as follows: If$x\neq 0$, then$v_{p}\left(x\right)$is the greatest integer k such that$\frac {x}{p^{k}}$can be written as a fraction of two integers with the denominator not being divisible by$p$. Besides, we set$v_{p}\left(0\right) = + \infty$, where$+ \infty$is just a symbol satisfying$+ \infty > a$and$+ \infty + a = + \infty$for any integer$a$(what we will mainly need is that$v_{p}\left(0\right) > v_{p}\left(x\right)$for any nonzero x). We can easily see how to compute$v_{p}\left(x\right)$for rationals$x\neq 0$: If x is a nonzero integer, then$v_{p}\left(x\right)$is the greatest integer k such that$p^{k}$divides x (particularly,$v_{p}\left(x\right) = 0$if p doesn't divide x); if x is a fraction of two nonzero integers, say$x = \frac {a}{b}$with integers a and b, then$v_{p}\left(x\right) = v_{p}\left(a\right) - v_{p}\left(b\right)$. Note that there is a simple way to interpret the sign of the p-adic evaluation$v_{p}\left(x\right)$of a rational number x: If we write x as a reduced fraction (i. e. a fraction with numerator and denominator coprime; if x is an integer, then just write it in the form$x = \frac {x}{1}$), and it turns out that the numerator is divisible by p, then$v_{p}\left(x\right) > 0$; if neither the numerator nor the denominator is divisible by p, then$v_{p}\left(x\right) = 0$; if the denominator is divisible by p, then$v_{p}\left(x\right) < 0$. It is rather easy to prove that for any two rational numbers x and y, we have$v_{p}\left(xy\right) = v_{p}\left(x\right) + v_{p}\left(y\right)$and$v_{p}\left(x + y\right)\geq\min\left(v_{p}\left(x\right);\;v_{p}\left(y\right)\right)$. [color=blue][b]2. Working with fractions modulo p[/b][/color] We will also need some familiarity with fractions in$\mathbb{Z}_{p}$. The main idea is to extend the notion of congruence modulo p from integers to rational numbers with nonnegative p-adic evaluation: If x and y are two rational numbers such that$v_{p}\left(x\right)\geq 0$and$v_{p}\left(y\right)\geq 0$, then we say that$x\equiv y\mod p$if and only if$v_{p}\left(x - y\right) > 0$. Thus we have defined an equivalence relation (that it is an equivalence relation is easy to prove - do it for yourself) on the set of all rational numbers with nonnegative p-adic evaluation. Now one could expect that, in this way, we would obtain a kind of new group of remainders, say$\mathbb{Q}_{p}$- but in fact, we get nothing but our old familiar$\mathbb{Z}_{p}$, since for every rational number x, there is one and only one integer n satisfying$0\leq n < p$such that$x\equiv n\mod p$(this is again easy to prove). Hence, you can work with rational numbers whose p-adic evaluation is nonnegative in the same way as you work with remainders modulo p. This also means that you can uniquely divide modulo p. [A nice application of this is [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=44573]problem 4 of the IMO 2005[/url] - see Fedor Petrov's proof in post #2.] [color=blue][b]3. Generalization of Wolstenholme's Theorem[/b][/color] Now, the problem A 23 asks us to show that if p is a prime number such that$p\geq 5$, then$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k}\right)\geq 2$. This is a particular case (u = 1) of the following result: [color=blue][b]Theorem 1.[/b] If p is a prime number and u is an odd integer such that$p\geq u + 3$, then$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2$.[/color] [i]Proof of Theorem 1.[/i] We will first work in$\mathbb{Q}$and only later come over into$\mathbb{Z}_{p}$. Note that p > 2 (since$p\geq u + 3$). We start with the Gauss trick:$2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {1}{k^{u}} + \sum_{k = 1}^{p - 1}\frac {1}{\left(p - k\right)^{u}} = \sum_{k = 1}^{p - 1}\left(\frac {1}{k^{u}} + \frac {1}{\left(p - k\right)^{u}}\right) = \sum_{k = 1}^{p - 1}\frac {k^{u} + \left(p - k\right)^{u}}{k^{u}\left(p - k\right)^{u}}$. Now denote$s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}$for every$k\in\left\{1,2,...,p-1\right\}$. Obviously,$s_k$is an integer for every$k$. We can expand$\left(p - k\right)^{u}$according to the binomial formula:$\left(p - k\right)^{u}=\sum_{i=0}^u\left(-1\right)^{u-i}\binom{u}{i}p^ik^{u-i}=\left(-1\right)^{u-0}\binom{u}{0}p^0k^{u-0}+\left(-1\right)^{u-1}\binom{u}{1}p^1k^{u-1}+\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^ik^{u-i}=\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}=\left(-1\right)^uk^u+\left(-1\right)^{u-1}upk^{u-1}+p^2s_k=\left(-1\right)k^u+1upk^{u-1}+p^2s_k$(since u is odd, so that$\left(-1\right)^u=-1$and$\left(-1\right)^{u-1}=1$)$=-k^u+upk^{u-1}+p^2s_k$. Thus,$k^u+\left(p-k\right)^u = upk^{u-1}+p^2s_k$for every$k\in\left\{1,2,...,p-1\right\}$, and therefore$2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}} = \sum_{k = 1}^{p - 1}\frac {k^{u} + \left(p - k\right)^{u}}{k^{u}\left(p - k\right)^{u}} = \sum_{k = 1}^{p - 1}\frac {upk^{u-1}+p^2s_k}{k^{u}\left(p - k\right)^{u}} = \sum_{k = 1}^{p - 1} p \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}= p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$. But since p > 2, we have$v_{p}\left(2\right) = 0$, so that$v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(2\right) + v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)$. On the other hand,$v_{p}\left(2\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left( p \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) = v_{p}\left(p\right) + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)= 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)$. Thus,$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = 1 + v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)$. Hence, instead of showing$v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2$, it will be enough to prove$v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right)\geq 1$. This is equivalent to$v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) > 0$, i. e. to$\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv 0\mod p$. Now we start working in$\mathbb{Z}_{p}$. In fact, we can consider all the fractions$\frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$in$\mathbb{Z}_{p}$since they have nonnegative p-adic evaluations (because their denominators,$k^{u}\left(p - k\right)^{u}$, are not divisible by p, since$1\leq k\leq p - 1$and p is a prime). The numerators$uk^{u-1}+ps_k$of these fractions can be simplified to$uk^{u - 1}$, since$p\equiv 0\mod p$, and thus all terms containing p can be omitted. Also, the denominators can be simplified: Since$p - k\equiv - k\mod p$, we have$k^{u}\left(p - k\right)^{u}\equiv k^{u}\left( - k\right)^{u} = \left( - 1\right)^{u}k^{2u}$. Hence,$\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\sum_{k = 1}^{p - 1}\frac {uk^{u - 1}}{\left( - 1\right)^{u}k^{2u}}\equiv\frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p - 1}k^{ - u - 1}\mod p$. But we are working in$\mathbb{Z}_{p}$, and thus, by Fermat's small theorem,$k^{p - 1}\equiv 1\mod p$for every integer k such that$1\leq k\leq p - 1$. Thus,$k^{ - u - 1}\equiv k^{ - u - 1}k^{p - 1} = k^{p - u - 2}\mod p$, and this sum becomes$\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p - 1}k^{p - u - 2}\mod p$. Now,$p - u - 2\geq 1$(since$p\geq u + 3$) and$p - u - 2\leq p - 2$. Also, p is an odd prime (since p is a prime and p > 2). Now, according to http://www.problem-solving.be/pen/viewtopic.php?t=676 part [b]a)[/b] (and also http://www.mathlinks.ro/Forum/viewtopic.php?t=40171 ), we have: [color=blue][b]Theorem 2.[/b] If p is an odd prime and$\rho$is an integer such that$1\leq\rho\leq p - 2$, then$p\mid\sum_{k = 1}^{p - 1}k^{\rho}$.[/color] Applying this Theorem 2 to our prime p and$\rho = p - u - 2$(we know that p is an odd prime and$\rho = p - u - 2$satisfies$1\leq p - u - 2\leq p - 2$), we get$p\mid\sum_{k = 1}^{p - 1}k^{p - u - 2}$, so that$\sum_{k = 1}^{p - 1}k^{p - u - 2}\equiv 0\mod p$, and thus$\sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}\equiv\frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p - 1}k^{p - u - 2}\equiv\frac {u}{\left( - 1\right)^{u}}\cdot 0 = 0\mod p\$.

This completes the proof of Theorem 1.

[EDIT: Made the proof of Theorem 1 slightly more formal. See [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=46121]the other post[/url] for the old version.]

Darij

----------------------------------------------------------------------------------------------------------------------------



### Source: geocities.com/de/darij_grinberg

( geocities.com/de)