Considering the number of all possible arrangements, it will be $C_{p^{2}}^{p}$. We have $p$ "bad" arrangements. So we must prove that: $C_{p^{2}}^{p}-p \vdots p^{5} \Leftrightarrow$ $\frac{p^{2}\cdot(p^{2}-1)\cdot\ldots(p^{2}-p+1)}{p!}-p \vdots p^{5}\Leftrightarrow$ $\frac{p^{2}\cdot(p^{2}-1)\cdot\ldots(p^{2}-p+1)-p\cdot p!}{p!}$ $\vdots$ $p^{5}\Leftrightarrow$ $\frac{p(p^{2}-1)(p^{2}-2)\ldots (p^{2}-(p-1))-p!}{(p-1)!}$ $\vdots$ $p^{5}$. Since $p$ is a prime number, we ignore $(p-1)!$. Dividing by $p$, we must prove that: $(p^{2}-1)\ldots (p^{2}-p+1)-(p-1)!$ $\vdots$ $p^{4}$. In the process of opening the brakets, if we select 2 $p^{2}$'s, then the whole product will be divisible by $p^{4}$. So, we must prove that: $p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{4}$. Since $(-1)^{p-1}=1$, then it suffices to prove that: $\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1}$ $\vdots$ $p^{2}\Leftrightarrow$ $(p-1)!\cdot(1+\frac{1}{2}+\ldots+\frac{1}{p-1})$ $\vdots$ $p^{2}$ The last follows immediately from Wolstenholme's Theorem.

I would just like to comment on the official solution for this problem. Apparently, everything that Freemind wrote above is worth 3 marks, and the organisers had expected the contestants to prove Wolstenholme's Theorem for the next 4 marks, without realising that it was a well-known theorem. As a result, according to the official guidelines, anybody who quotes Wolstenholme's Theorem in addition to whatever is written above is awarded 7 marks, whereas those who do not know that it is a well-known result are awarded 3.

That is a little strange. Actually, up till yesterday, i didn't know that it is a result of Wolstenholme. I just met this in another problem, so i thought it should be known problem, and starting looking for it. I discovered in a book that it was actually a theorem.

I know the Wolstenholme's theorem. but i can't und how freemind brought that fractional form from that product form? can anybody clr me?

mahbub, Wolstenholme states that the numerator of $1+\frac{1}{2}+\ldots+\frac{1}{p-1}$ is divisible by $p^{2}$. Since $p$ is a prime number, the denominator will not be divisible by $p$. Let $1+\frac{1}{2}+\ldots+\frac{1}{p-1}=\frac{M}{N}$. Then $M=p^{2}m$, $N=(p-1)!$. Multiplying by $(p-1)!$ we get $mp^{2}$. I didn't put the condition that $(M,N)=1$, because ii isn't necessary. That's why we may take simply $N=(p-1)!$.

freemind wrote: So, we must prove that: $p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{5}$ I think mahbub wants to know how you arrive to this step instead of Wolstenholme Theorem

shyong is correct!

shyong wrote: freemind wrote: So, we must prove that: $p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{5}$ I think mahbub wants to know how you arrive to this step instead of Wolstenholme Theorem Yes, I did a mechanical mistake . I edited already. I wrote we must prove that is divisible by $p^{4}$, but in the relation, I wrote $p^{5}$. I think everything is clear now.

freemind wrote: ${p(p^{2}-1)(p^{2}-2)\ldots (p^{2}-(p-1))-p!}{(p-1)!}$ $\vdots$ $p^{5}$. $p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{4}$. How does the second line comes from the first line? I mean by which transformation u got the second line? [I hope u can understand my Q now )

Sorry! I didn't put a \frac !

How many marks do i get, if I proved half of the Wolstenholme's Theorem. I proved that $p|\sum_{i=1}^{p-1}\frac{1}i$ but I couldn't prove it for $p^2$

Sorry, but thats not half of it... I would say it is not even a part of it... However, about marks, i dont really know...

Have you read the first posts!! They finished the problem using Wolstenholme's Theorem, I did the same, but i didn't knew it was a known result. But i didn´t stop at that point, I did a little bit more than that. So it really is a part of it.

Quote: I proved that $p|\sum_{i=1}^{p-1}\frac{1}{i}$ but I couldn't prove it for $p^2$ What I meant is that it is not even half of Wolstenholme's theorem, in fact showing that $p$ divides it is trivial while for $p^2$ it is not trivial at all!!! So maybe the problem ended that way, but if you didnt prove Wolstenholme or neither mentioned you wont get many marks!!! Check the marking scheme. I personally checked part of your test and i can tell you wont get lot of marks here. BTW A theorem is a theorem, you cannot talk about "half" of a theorem, in my opinion. No more spam.

freemind wrote: , we must prove that: $(p^{2}-1)\ldots (p^{2}-p+1)-(p-1)!$ $\vdots$ $p^{4}$. So, we must prove that: $p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{4}$. . Could you explain how you reach to the second from the first ?? I can't see this

silouan wrote: freemind wrote: , we must prove that: $(p^{2}-1)\ldots (p^{2}-p+1)-(p-1)!$ $\vdots$ $p^{4}$. So, we must prove that: $p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{4}$. . Could you explain how you reach to the second from the first ?? I can't see this When opening the braktes, if you choose 2 factors $p^{2}$, then their product with other $p-3$ terms, will be divisible by $p^{2}\cdot p^{2}=p^{4}$. So we must consider, when opening the brakets, only the terms containing one $p^{2}$, or no$p^{2}$. There is only one term containing no $p^{2}$. That is $(-1)(-2)\ldots (-(p-1))=(-1)^{p-1}\cdot(p-1)!$. If we choose one $p^{2}$ from some bracket, say from $p^{2}-k$, then it will be multiplied by $(-1)(-2)\ldots(-(k-1))(-(k+1))\ldots(p-1)=(-1)^{p-2}\frac{(p-1)!}{k}$. When considering the divisibility, the minus doesn't matter, since $(-1)^{p-1}(p-1)!-(p-1)!=0$

Thank you nice explanation and nice solution .

Via a counting argument, \[r=\binom{p^2}{p}-p\] We now want: \begin{align*} \frac{p^2\left(p^2-1\right)\cdots \left(p^2-p+1\right)}{p\left(p-1\right)!}\equiv p\pmod{p^5}\\\frac{\left(p^2-1\right)\cdots \left(p^2-p+1\right)}{\left(p-1\right)!}\equiv 1\pmod{p^4} \\ \left(p^2-1\right)\cdots \left(p^2-p+1\right)-\left(p-1\right)!\equiv 0\pmod{p^4} \\ p^2\left(-1\right)^{p-2}\left(\sum_{i=1}^{p-1}\frac{(p-1)!}{i}\right)+\left(-1\right)^{p-1}\left(p-1\right)!-\left(p-1\right)! \equiv 0\pmod{p^4}\\ -p^2\left(p-1\right)!\sum_{i=1}^{p-1}\frac{1}{i}\equiv 0\pmod{p^4}\end{align*} Which is true by Wolstenholme’s theorem.

How do you do mods with fractions? How does it work? For example, can you add fractions in mods, like $\frac{1}{2}+\frac{1}{3}\equiv\frac{5}{6} (mod ...)$ or something?

Once $m$ is coprime with $n$, it is invertible modulo $n$, so there exists its inverse, denoted $m^{-1}$ modulo $n$. To write $m^{-1} = \dfrac {1}{m}$ is just an issue of notation, thus allowed. As for your other question, yes, say you have $2^{-1}+3^{-1} \equiv a \pmod{n}$, where $\gcd(n,6)=1$. Multiply by $6$ to get $5=2+3 \equiv 6a \pmod{n}$. Since $6$ is invertible, we can also write $5\cdot 6^{-1} \equiv a \pmod{n}$, i.e. $2^{-1}+3^{-1} \equiv 5\cdot 6^{-1} \pmod{n}$.

So technically, $m^{-1}$ or $\frac{1}{m}$ are integers $mod n$ for $m,n$ relatively prime? Digressing a little, this means that $(\frac{a}{b})^2\equiv (a\cdot b^{-1})^2 \equiv 2(mod n)$ implies 2 is a quadratic residue of $n$? since $\frac{a}{b}$ is an integer?

Because $r={{p^2}\choose{p}}-p$ we can easily reduce it to $p^4 | \displaystyle\prod_{i=1}^{p-1} (p^2-i) - \displaystyle\prod_{i=1}^{p-1} (i) $. Expanding the first product out, it reduces to $p^2 | \displaystyle\sum_{i=1}^{p-1} \displaystyle\frac{(p-1)!}{i}$ which is equivalent to the Wolstenholme Lemma.

nice problem

here's a solution without using any theorem

It suffices to show that $\dbinom{p^2}{p} \equiv p\pmod{p^5}$ Expanding it,we get \begin{align*} \dfrac{p^2(p^2-1)\cdots (p^2-p+1)}{p!} &\equiv p\pmod{p^5}\\ (p^2-1)\cdots (p^2-p+1) &\equiv (p-1)!\pmod{p^4}\\ (p-1)! - p^2(p-1)!\left(1^{-1}+2^{-1}+\cdots +(p-1)^{-1}\right) &\equiv (p-1)! \pmod{p^4}\\ 1^{-1}+2^{-1}+\cdots +(p-1)^{-1} &\equiv 0 \pmod{p^2} \end{align*}which is just Wolstenholme's Theorem.$\blacksquare$

i think the number of way of placing is p^p ways because we start at 1 square (any) the second move you have p ways and next move will be p^2 and continue will we will have p^(p-1) and then we have p^p way which can divisble to p^5 because p>= 5 Please point where i false if there is a mistake