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] The following solution is [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=48300]my solution from MathLinks[/url], slightly rewritten: 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 "nonnegative" 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 nonnegative 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 other words, we claim that the number $\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$ is the smallest possible nonnegative value of the term $\sqrt{2p}-\sqrt{x}-\sqrt{y}$ for positive integers x and y with $x\leq y$, and this value is achieved only for $x=\frac{p-1}{2}$ and $y=\frac{p+1}{2}$. In order to prove this claim, we will verify the following two assertions: [i]Assertion 1.[/i] The two numbers $\frac{p-1}{2}$ and $\frac{p+1}{2}$ are positive integers and satisfy $\frac{p-1}{2}\leq\frac{p+1}{2}$, and the number $\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$ is nonnegative. [i]Assertion 2.[/i] If $x$ and $y$ are positive integers satisfying $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}}$, then $x=\frac{p-1}{2}$ and $y=\frac{p+1}{2}$. [i]Proof of Assertion 1.[/i] 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 obviously positive, and satisfy $\frac{p-1}{2}\leq\frac{p+1}{2}$. Besides, $\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$ is indeed nonnegative (since 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). Hence, Assertion 1 is proven. [i]Proof of Assertion 2.[/i] Let $x$ and $y$ be 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 proving Assertion 2. 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$, this yields $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 thus Assertion 2 is proven. Clearly, Assertion 2 yields: [i]Assertion 3.[/i] Let $x$ and $y$ be positive integers such that $x\leq y$ and such that $\sqrt{2p}-\sqrt{x}-\sqrt{y}$ is nonnegative. If $\left(x,y\right)\neq\left(\frac{p-1}{2},\frac{p+1}{2}\right)$, then $\sqrt{2p}-\sqrt{x}-\sqrt{y}>\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$. (In fact, otherwise we would have $\sqrt{2p}-\sqrt{x}-\sqrt{y}\leq\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$, and thus Assertion 2 would yield $x=\frac{p-1}{2}$ and $y=\frac{p+1}{2}$, which contradicts $\left(x,y\right)\neq\left(\frac{p-1}{2},\frac{p+1}{2}\right)$.) Now, we claimed that the number $\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$ is the smallest possible nonnegative value of the term $\sqrt{2p}-\sqrt{x}-\sqrt{y}$ for positive integers x and y with $x\leq y$, and this value is achieved only for $x=\frac{p-1}{2}$ and $y=\frac{p+1}{2}$. We now see that this claim is true, since the number $\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$ is indeed the nonnegative value of the term $\sqrt{2p}-\sqrt{x}-\sqrt{y}$ at $\left(x,y\right)=\left(\frac{p-1}{2},\frac{p+1}{2}\right)$ (by Assertion 1), and any nonnegative value of the term $\sqrt{2p}-\sqrt{x}-\sqrt{y}$ for positive integers $x$ and $y$ such that $x\leq y$ is larger than $\sqrt{2p}-\sqrt{\frac{p-1}{2}}-\sqrt{\frac{p+1}{2}}$ unless $\left(x,y\right)=\left(\frac{p-1}{2},\frac{p+1}{2}\right)$ (by Assertion 3). Hence, 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 $\mathbb{N}$ denote the set $\left\{1,2,3,\ldots\right\}$. 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$ and $u\geq 0$). 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}\mod p$. 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$. (Here and in the following, $\mathbb{N}$ denotes the set $\left\{1,2,3,\ldots\right\}$.) 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}\text{ 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 relies on computations with operators acting on sequences. It requires some basics of linear algebra (vector spaces, linear operators and endomorphism rings) that should be known to IMO participants. I will first introduce some notations: 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^{\mathbb{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}}$ and 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)\overline{u}}_{=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 OLD VERSION v2 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 an updated 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 modulo $p$, you can uniquely divide by any integer not divisible by $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 (namely, the $u = 1$ case) 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$ and $u\geq 0$, 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$ and $u\geq 0$). 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 $2$ isn't divisible by $p$ (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) = \underbrace{v_{p}\left(2\right)}_{=0} + 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) = \underbrace{v_{p}\left(p\right)}_{=1} + 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, for every $k\in\left\{1,2,...,p-1\right\}$, we can consider the fraction $\frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$ in $\mathbb{Z}_{p}$, since it has a nonnegative $p$-adic evaluation (because its denominator, $k^{u}\left(p - k\right)^{u}$, is not divisible by $p$, since $1\leq k\leq p - 1$ and since $p$ is a prime). Modulo $p$, the numerator $uk^{u-1}+ps_k$ of this fraction can be simplified to $uk^{u - 1}$ (since $p\equiv 0\mod p$, and thus all terms containing $p$ can be omitted). Also, the denominator 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} \mod p$. Hence, $\frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv \frac {uk^{u-1}}{\left(-1\right)^u k^{2u}}\mod p$. Therefore, [color=green][b](1)[/b][/color] $\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}} = \sum_{k = 1}^{p - 1}\frac {uk^{-u - 1}}{\left( - 1\right)^{u}} = \frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p - 1}k^{ - u - 1}\mod p$. But 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 the relation [color=green][b](1)[/b][/color] 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}} \underbrace{\sum_{k = 1}^{p - 1}k^{p - u - 2}}_{\equiv 0\mod p} \equiv \frac {u}{\left( - 1\right)^{u}}\cdot 0 = 0\mod p$. This completes the proof of Theorem 1. [color=blue][b]4. A divisibility by $p^3$[/b][/color] We can use almost the same tactics to prove a similar result: [color=blue][b]Theorem 3.[/b] If $p$ is a prime number such that $p>3$, then $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)\geq 3$.[/color] [i]Proof of Theorem 3.[/i] It is known that for every integer $i$ such that $00$ (since $p>3>2$). Set $u=p$. Also, 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$. Then, every $k\in\left\{1,2,...,p-1\right\}$ satisfies $s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}=\sum_{i=2}^p\left(-1\right)^{p-i}\binom{p}{i}p^{i-2}k^{p-i}$ (since $u=p$) $=\sum_{i=2}^{p-1}\left(-1\right)^{p-i}\underbrace{\binom{p}{i}}_{\substack{\equiv 0\mod p,\\ \text{ since } 00}}k^{p-p}$ $\equiv \underbrace{\sum_{i=2}^{p-1}\left(-1\right)^{p-i}0p^{i-2}k^{p-i}}_{=0}+\underbrace{\left(-1\right)^{p-p}\binom{p}{p}0k^{p-p}}_{=0}=0+0=0\mod p$. We will first work in $\mathbb{Q}$ and only later come over into $\mathbb{Z}_{p}$. Just as in the proof of Theorem 1, we can show that [color=green][b](2)[/b][/color] $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)$. Since $u=p$, we have $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)$ and $v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) = v_{p}\left( \sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} \right)$ $ = v_{p}\left( p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$ (since $\sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} \frac {p\left(k^{p-1}+s_k\right)}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} p\cdot \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} = p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$) $ = \underbrace{v_p\left(p\right)}_{=1} + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) = 1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$. Thus, [color=green][b](2)[/b][/color] becomes $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 1 + \left(1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\right)$. In other words, $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 2 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$. Hence, instead of showing $v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{p}}\right)\geq 3$, it will be enough to prove $v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\geq 1$. This is equivalent to $v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) > 0$, i. e. to $\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv 0\mod p$. Now we start working in $\mathbb{Z}_{p}$. In fact, for every $k\in\left\{1,2,...,p-1\right\}$, we can consider the fraction $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$ in $\mathbb{Z}_{p}$, since it has a nonnegative $p$-adic evaluation (because its denominator, $k^p\left(p - k\right)^p$, is not divisible by $p$, since $1\leq k\leq p - 1$ and since $p$ is a prime). Modulo $p$, the numerator $k^{p-1}+s_k$ of this fraction can be simplified to $k^{p-1}$ (since $s_k\equiv 0\mod p$, and thus the term $s_k$ can be omitted). Also, the denominator can be simplified: Since $p - k\equiv - k\mod p$, we have $k^p\left(p - k\right)^p\equiv k^p\left( - k\right)^p = \left( - 1\right)^pk^{2p} \mod p$. Hence, $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} \mod p$. Therefore, [color=green][b](3)[/b][/color] $\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} = \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{k^{2p}} \mod p$. But by Fermat's small theorem, $k^p\equiv k\mod p$ for every integer $k$. Thus, $\left(k^p\right)^2\equiv k^2\mod p$, so that $k^{2p}=\left(k^p\right)^2\equiv k^2\mod p$. Hence, the relation [color=green][b](3)[/b][/color] becomes $\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\underbrace{\frac {k^{p-1}}{k^2}}_{ = k^{\left(p-1\right)-2}=k^{p-3}} = \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}k^{p-3} \mod p$. Now, $p-3\geq 1$ (since $p>3$ yields $p-3>0$, and $p-3\in\mathbb{Z}$) and $p-3\leq p-2$. Also, $p$ is an odd prime (since $p$ is a prime and $p > 2$). Applying Theorem 2 to our prime $p$ and $\rho = p - 3$ (we know that $p$ is an odd prime and $\rho = p-3$ satisfies $1\leq p-3\leq p - 2$), we get $p\mid\sum_{k = 1}^{p - 1}k^{p - 3}$, so that $\sum_{k = 1}^{p - 1}k^{p - 3}\equiv 0\mod p$, and thus $\sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \underbrace{\sum_{k = 1}^{p - 1}k^{p-3}}_{\equiv 0\mod p} \equiv \frac{1}{\left(-1\right)^p}\cdot 0 = 0\mod p$. This completes the proof of Theorem 3. [EDIT: Made the proof of Theorem 1 slightly more formal, and added section 4. See [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=46121]the other thread[/url] for the old version of this post.] 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 an updated 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 valuation[/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 the so-called [i]$p$-adic valuation of $x$[/i]. This valuation 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 ratio 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$. (The main thing we will need about $+ \infty$ 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$ (thus, in particular, we have $ v_{p}\left(x\right) = 0$ if $p$ doesn't divide $x$). * If $x$ is a ratio of two nonzero integers, say $ x = \frac{a}{b}$ with nonzero 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 valuation $ 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$. A [i]$p$-integer[/i] shall mean a rational number $x$ satisfying $v_p\left(x\right) \geq 0$. In particular, every integer is a $p$-integer. Moreover, any fraction of integers is a $p$-integer if its denominator is coprime to $p$. 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)$. Thus, the sum and the product of two $p$-integers are $p$-integers again. Hence, it is not hard to see that any sum or product of finitely many $p$-integers is a $p$-integer, and that a difference of two $p$-integers is always a $p$-integer. (In the language of abstract algebra, this is saying that the $p$-integers form a subring of $\mathbb{Q}$.) [color=blue][b]2. Working with fractions modulo $p$[/b][/color] I will use the notation $\mathbb{Z}_{p}$ for the ring $\mathbb{Z} / p\mathbb{Z}$ (that is, the ring of integers modulo $p$). 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 $p$-integers: If $x$ and $y$ are two $p$-integers, then we say that $x\equiv y\mod p$ (in words: "$x$ is congruent to $y$ modulo $p$") if and only if $v_{p}\left(x - y\right) > 0$. Thus we have defined a relation ("congruence modulo $p$") on the set of all $p$-integers. This relation is an equivalence relation (this is easy to prove; do it!). Moreover, if $x$ and $y$ are two integers, then $x \equiv y \mod p$ with respect to this new equivalence relation if and only if $x \equiv y \mod p$ in the usual sense (i.e., we have $p \mid x-y$ in $\mathbb{Z}$). This fact allows us to use the same notation for both equivalence relations without worrying about possible ambiguity. It is easy to see that this equivalence relation has the same properties as the classical "congruence modulo $p$" relation on integers: * If $a$, $b$, $c$ and $d$ are $p$-integers, and if $a \equiv b \mod p$ and $c \equiv d \mod p$, then $a+c \equiv b+d \mod p$ and $a-c \equiv b-d \mod p$ and $ac \equiv bd \mod p$. In other words, congruences modulo $p$ between $p$-integers can be added, subtracted and multiplied just as congruences between integers. * The same holds for larger sums: i.e., if $a_1, a_2, \ldots, a_j, b_1, b_2, \ldots, b_j$ are $p$-integers, and if every $i$ satisfies $a_i \equiv b_i \mod p$, then $\sum\limits_{i=1}^j a_i \equiv \sum\limits_{i=1}^j b_i \mod p$. * If $a$, $b$, $c$ and $d$ are $p$-integers such that $v_p\left(b\right) = 0$ and $v_p\left(d\right) = 0$, and if $a \equiv b \mod p$ and $c \equiv d \mod p$, then $a/c \equiv b/d \mod p$. In other words, congruences modulo $p$ between $p$-integers can be divided by one another, as long as the $p$-integers we are dividing by have $p$-adic valuations equal to $0$. We shall refer to this fact as the [i]division rule[/i]. Recall that congruence modulo $p$ is an equivalence relation on the set of $p$-integers. Let $F_p$ denote the set of equivalence classes of this equivalence relation. One might expect that $F_p$ is larger than $\mathbb{Z}_p$, seeing that the equivalence classes that comprise $F_p$ consist of $p$-integers whereas the equivalence classes that comprise $\mathbb{Z}_p$ consist of integers only. But in fact, it turns out that $F_p$ is in bijection with $\mathbb{Z}_p$. Indeed, it is easy to prove that for every $p$-integer $x$, there is one and only one integer $n$ satisfying $0\leq n < p$ such that $x\equiv n\mod p$. Thus, every equivalence class in $F_p$ contains exactly one of the integers $0, 1, \ldots, p-1$, and thus corresponds to a unique equivalence class in $\mathbb{Z}_p$. Equivalence classes in $F_p$ can be added, subtracted and multiplied (just as in $\mathbb{Z}_p$), and these operations match precisely the analogous operations in $\mathbb{Z}_p$ (that is, if you add two equivalence classes in $F_p$, then the corresponding class in $\mathbb{Z}_p$ is obtained by adding the classes in $\mathbb{Z}_p$ that correspond to the two addends; and similarly for subtraction and multiplication). Furthermore, if $x$ and $y$ are two equivalence classes in $F_p$, then $x/y$ is a well-defined equivalence class in $F_p$ provided that $y$ is the equivalene class of a $p$-integer $u$ with $v_p\left(u\right) = 0$. (Again, it is constructed as usual: Pick an element $a \in x$ and an element $b \in y$, and form the equivalence class of the rational number $a/b$.) Hence, you can work with $p$-integers modulo $p$ in the same way as you work with integers modulo $p$. This also means that modulo $p$, you can uniquely divide by any integer not divisible by $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 (namely, the $ u = 1$ case) of the following result: [color=blue][b]Theorem 1.[/b] Let $ p$ be a prime number, and $ u$ be an odd integer such that $ p\geq u + 3$ and $ u\geq 0$. Then, $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right)\geq 2$.[/color] [i]Proof of Theorem 1.[/i] We have $ p > 2$ (since $ p\geq u + 3$ and $ u\geq 0$). 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}{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, define $ 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}}$. Hence, $ 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) = \underbrace{v_{p}\left(p\right)}_{=1} + 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)$. But since $ 2$ isn't divisible by $ p$ (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) = \underbrace{v_{p}\left(2\right)}_{=0} + 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)$. Comparing these two equalities, we get $ 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$. Here, we are using the fact that for every $ k\in\left\{1,2,...,p-1\right\}$, the fraction $ \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$ is a $p$-integer (because its denominator, $ k^{u}\left(p - k\right)^{u}$, is not divisible by $ p$, since $ 1\leq k\leq p - 1$ and since $ p$ is a prime), and therefore it makes sense to say that the sum of all these fractions is $\equiv 0 \mod p$. Let us now look more closely at such a fraction $\frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}}$ (with $k \in \left\{1,2,\ldots,p-1\right\}$). The numerator $ uk^{u-1}+ps_k$ of this fraction is congruent to $ uk^{u - 1}$ modulo $p$ (since $ p\equiv 0\mod p$, and thus all terms containing $ p$ can be omitted). Also, the denominator can be simplified modulo $p$: 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} \mod p$. Dividing the congruence $uk^{u-1}+ps_k \equiv uk^{u-1} \mod p$ by the latter congruence, we obtain $ \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \equiv \frac {uk^{u-1}}{\left(-1\right)^u k^{2u}}\mod p$ (here, we have applied the division rule, since the rational numbers $k^{u}\left(p - k\right)^{u}$ and $\left(-1\right)^u k^{2u}$ have $p$-adic valuation $0$). Therefore, [color=green][b](1)[/b][/color] $ \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}} = \sum_{k = 1}^{p - 1}\frac {uk^{-u - 1}}{\left( - 1\right)^{u}} = \frac {u}{\left( - 1\right)^{u}}\sum_{k = 1}^{p - 1}k^{ - u - 1}\mod p$. But by Fermat's Little Theorem, $ k^{p - 1}\equiv 1\mod p$ for every integer $ k$ such that $ 1\leq k\leq p - 1$. Thus, every such $k$ satisfies $ k^{ - u - 1}\equiv k^{ - u - 1}k^{p - 1} = k^{p - u - 2}\mod p$, and the relation [color=green][b](1)[/b][/color] 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}} \underbrace{\sum_{k = 1}^{p - 1}k^{p - u - 2}}_{\equiv 0\mod p} \equiv \frac {u}{\left( - 1\right)^{u}}\cdot 0 = 0\mod p$. This completes the proof of Theorem 1. [color=blue][b]4. A divisibility by $ p^3$[/b][/color] We can use almost the same tactics to prove a similar result: [color=blue][b]Theorem 3.[/b] Let $ p$ be a prime number such that $ p>3$. Then, $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)\geq 3$.[/color] [i]Proof of Theorem 3.[/i] It is known that for every integer $ i$ such that $ 00$ (since $ p>3>2$). Set $ u=p$. Also, 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$. Then, every $ k\in\left\{1,2,...,p-1\right\}$ satisfies $ s_k=\sum_{i=2}^u\left(-1\right)^{u-i}\binom{u}{i}p^{i-2}k^{u-i}=\sum_{i=2}^p\left(-1\right)^{p-i}\binom{p}{i}p^{i-2}k^{p-i}$ (since $ u=p$) $ =\sum_{i=2}^{p-1}\left(-1\right)^{p-i}\underbrace{\binom{p}{i}}_{\substack{\equiv 0\mod p,\\ \text{ since } 00}}k^{p-p}$ $ \equiv \underbrace{\sum_{i=2}^{p-1}\left(-1\right)^{p-i}0p^{i-2}k^{p-i}}_{=0}+\underbrace{\left(-1\right)^{p-p}\binom{p}{p}0k^{p-p}}_{=0}=0+0=0\mod p$. Just as in the proof of Theorem 1, we can show that [color=green][b](2)[/b][/color] $ 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)$. Since $ u=p$, we have $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{u}}\right) = v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right)$ and $ v_{p}\left( \sum_{k = 1}^{p - 1} \frac {uk^{u-1}+ps_k}{k^{u}\left(p - k\right)^{u}} \right) = v_{p}\left( \sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} \right)$ $ = v_{p}\left( p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$ (since $ \sum_{k = 1}^{p - 1} \frac {pk^{p-1}+ps_k}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} \frac {p\left(k^{p-1}+s_k\right)}{k^p\left(p - k\right)^p} = \sum_{k = 1}^{p - 1} p\cdot \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} = p\cdot \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$) $ = \underbrace{v_p\left(p\right)}_{=1} + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) = 1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$. Thus, [color=green][b](2)[/b][/color] becomes $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 1 + \left(1 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\right)$. In other words, $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^p}\right) = 2 + v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)$. Hence, instead of showing $ v_{p}\left(\sum_{k = 1}^{p - 1}\frac {1}{k^{p}}\right)\geq 3$, it will be enough to prove $ v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right)\geq 1$. This is equivalent to $ v_p\left( \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \right) > 0$, i.e., to $ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv 0\mod p$. Here, we are using the fact that for each $k \in \left\{1,2,\ldots,p-1\right\}$, the fraction $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$ is a $p$-integers (because its denominator, $ k^p\left(p - k\right)^p$, is not divisible by $ p$, since $ 1\leq k\leq p - 1$ and since $ p$ is a prime), and thus it makes sense to speak of congruence modulo $p$ for the sum of these fractions. Let us study such a fraction $\frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p}$ (with $k \in \left\{1,2,\ldots,p-1\right\}$) more closely: Its numerator $ k^{p-1}+s_k$ is congruent to $ k^{p-1}$ modulo $p$ (since $ s_k\equiv 0\mod p$, and thus the term $ s_k$ can be omitted). Also, the denominator can be simplified: Since $ p - k\equiv - k\mod p$, we have $ k^p\left(p - k\right)^p\equiv k^p\left( - k\right)^p = \left( - 1\right)^pk^{2p} \mod p$. Hence, $ \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} \mod p$ (by the division rule). Therefore, [color=green][b](3)[/b][/color] $ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{\left( - 1\right)^pk^{2p}} = \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\frac {k^{p-1}}{k^{2p}} \mod p$. But by Fermat's Little Theorem, $ k^p\equiv k\mod p$ for every integer $ k$. Thus, $ \left(k^p\right)^2\equiv k^2\mod p$, so that $ k^{2p}=\left(k^p\right)^2\equiv k^2\mod p$. Hence, for every $k \in \left\{1,2,\ldots,p-1\right\}$, we have $\frac{k^{p-1}}{k^{2p}} \equiv \frac{k^{p-1}}{k^2} \mod p$ (here we used the division rule again, because $k^{2p}$ and $k^2$ are rational numbers with $p$-adic valuation $0$). Hence, the relation [color=green][b](3)[/b][/color] becomes $ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}\underbrace{\frac {k^{p-1}}{k^2}}_{ = k^{\left(p-1\right)-2}=k^{p-3}} = \frac{1}{\left(-1\right)^p} \sum_{k = 1}^{p - 1}k^{p-3} \mod p$. Now, $ p-3\geq 1$ (since $ p>3$ yields $ p-3>0$, and $ p-3\in\mathbb{Z}$) and $ p-3\leq p-2$. Also, $ p$ is an odd prime (since $ p$ is a prime and $ p > 2$). Applying Theorem 2 to our prime $ p$ and $ \rho = p - 3$ (we know that $ p$ is an odd prime and $ \rho = p-3$ satisfies $ 1\leq p-3\leq p - 2$), we get $ p\mid\sum_{k = 1}^{p - 1}k^{p - 3}$, so that $ \sum_{k = 1}^{p - 1}k^{p - 3}\equiv 0\mod p$, and thus $ \sum_{k = 1}^{p - 1} \frac {k^{p-1}+s_k}{k^p\left(p - k\right)^p} \equiv \frac{1}{\left(-1\right)^p} \underbrace{\sum_{k = 1}^{p - 1}k^{p-3}}_{\equiv 0\mod p} \equiv \frac{1}{\left(-1\right)^p}\cdot 0 = 0\mod p$. This completes the proof of Theorem 3. [EDIT: Made the proof of Theorem 1 slightly more formal, and added section 4. See [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=46121]the other thread[/url] for the old version of this post. EDIT 2: Improved the exposition of $p$-integers and their congruence significantly.] Darij ---------------------------------------------------------------------------------------------------------------------------