Darij's posts on the PEN forum: http://www.mathlinks.ro/Forum/index.php?f=456 (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 http://www.mathlinks.ro/Forum/viewtopic.php?t=150712 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 http://www.mathlinks.ro/Forum/viewtopic.php?t=150400 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 http://www.mathlinks.ro/Forum/viewtopic.php?t=150392 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 http://www.mathlinks.ro/Forum/viewtopic.php?t=150703 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. Read [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=849758#849758]http://www.mathlinks.ro/Forum/viewtopic.php?t=150713 post #2[/url] (or [url=http://www.problem-solving.be/pen/viewtopic.php?p=1004#1004]http://www.problem-solving.be/pen/viewtopic.php?t=347 post #2[/url]) until equation [color=green][b](1)[/b][/color], which states that [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 http://www.mathlinks.ro/Forum/viewtopic.php?t=150814 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 ----------------------------------------------------------------------------------------------------------------------------