\documentclass{article}
\reversemarginpar
\usepackage{list,economic,latexsym,amssymb,amsmath,amsthm,russcorr}
\renewcommand\refname{References} 
\renewcommand\bibname{References}
\newtheorem*{Lemm}{Lemma}
\begin{document}
\section*{Solutions for \flqq Power Sums and Bernoulli Numbers\frqq}
Here you see the solutions for some problems.
Most of the solutions below were known to the jury before~--- but
not all!
%\footnote{I am not sure whether it is necessary to 
%write down the names of the
%participants who submitted the solutions similar to classical, but
%we can discuss it if you want.}. 
Later
I hope to choose the best solutions for all problems from the submitted 
works~--- that will be in fact the result of the conference.
You are encouraged to ask questions (by email: {\tt dotsenko@mccme.ru}).  

\z\p\p The proof is standard. Let us formulate an equivalent question: how many
times does the term $x_1^{a_1}\cdots x_k^{a_k}$ occur in
$(x_1+\dots+x_k)^n$? This number is equal to the number of ways to split
$n$ given brackets into $k$ groups: first group containing $a_1$ brackets,
second one containing $a_2$ of them,\dots, $k$th one containing $a_k$ of
them. Details are left to the reader.


\z\p\p One can easily find a simple combinatorial
interpretation for $[a]^n$ and $[a]_n$ for an integer $a$: for
example, $[a]_n$ is the number of ways to choose
a chairman, a deputy chairman, \dots, a "deputy$^{n-1}$ chairman"
in a committee of $a$ persons. 

{\bf Exercise. } Conclude the proof for integers $a,\,b$.

For general $a,b$ use the following fact: a polynomial in $a,b$ vanishes
in all integer points if and only all its coefficients are equal to 0.

\z Hint: show that both ${\binom n k}_q$ and the coefficients of the
left-hand side satisfy the same recurrence relation.

\z\label{a}\p The proof involves a very important method: calculus of
finite differences (see~\cite{FD}). The main idea is very simple: imagine
that you know a polynomial $Q(x)$ such that $Q(1)=0$ ("initial
condition") and $Q(x+1)-Q(x)=x^k$. Then $Q(x)=P_k(x)$:
$1^k+2^k+\dots+(n-1)^k=Q(2)-Q(1)+Q(3)-Q(2)+\dots+Q(n)-Q(n-1)=Q(n)$.
Let us show that such a polynomial of degree $k+1$ exists (and is
unique).
Let $Q(x)=q_0+q_1x+\dots+q_kx^k+q_{k+1}x^{k+1}$. Then
$Q(x+1)-Q(x)=(k+1)q_{k+1}
x^k+({\binom {k+1} 2}q_{k+1}+kq_k)x^{k-1}+\dots$, so it is clear
that $q_i$ can be easily found one by one from these equations (such a
situation is called "a system of linear equations with an upper triangular
matrix") and the $k+2$-tuple $(q_0,\dots,q_{k+1})$ is unique
(it is determined up to the "constant term" $q_0$, which is obtained from  
the "initial condition" ).

\p
\begin{center}
$P_1(x)=x(x-1)/2, P_2(x)=x(x-1)(2x-1)/6, P_3(x)=x^2(x-1)^2/4,$

$P_4(x)=x(x-1)(2x-1)(3x^2-3x-1)/30, P_5(x)=x^2(x-1)^2(2x^2-2x-1)/12$
\end{center}


%\z The proof is simply by induction (here we follow~\cite{CM}; some of the
%participants managed to find slightly more short and convenient proofs).
%
%$$
%S_{k+1}(n)+n^{k+1}=\sum_{j=0}^{n-1}(j+1)^{k+1}=\sum_{j=0}^{n-1}\sum_{p=0}^{k+1}
%{\binom {k+1} p}j^p=\sum_{p=0}^{k+1}{\binom{k+1}p}S_p(n).
%$$

%Define ${\widehat S}_k(n)$ by (1) with $B_i$ defined by (2). 
%Suppose inductively that $S_p(n)={\widehat S}_p(n)$ for
%${0\le p<k}$. Denote by $\Delta$ the difference $S_k(n)-{\widehat
%S}_k(n)$. The above equality gives us (note that it also gives another
%proof that $S_k$ is a polynomial):
%\begin{align*}
%n^{k+1}&=\sum_{p=0}^k{\binom{k+1}p}S_p(n)=\sum_{p=0}^k{\binom{k+1}p}{\widehat
%S}_p(n)+{\binom {k+1}k}\Delta\\
%     &=\sum_{p=0}^k{\binom{k+1}p}\frac1{p+1}\sum_{m=0}^p{\binom{p+1}m}B_m
%n^{p+1-m}+(k+1)\Delta\\
%      &=\sum_{0\le m\le p\le
%k}{\binom{k+1}p}{\binom{p+1}m}\frac{B_m}{p+1}n^{p+1-m}+(k+1)\Delta\\
%%      &=\sum_{0\le m\le p\le
%k}{\binom{k+1}p}{\binom{p+1}{p-m}}\frac{B_{p-m}}{p+1}n^{m+1}+(k+1)\Delta\\
%      &=\sum_{0\le m\le p\le
%k}{\binom{k+1}p}{\binom{p+1}{m+1}}\frac{B_{p-m}}{p+1}n^{m+1}+(k+1)\Delta\\
%      &=\sum_{0\le m\le k}\frac{n^{m+1}}{m+1}\sum_{m\le p\le
%k}{\binom{k+1}p}{\binom p m}B_{p-m}+(k+1)\Delta\\
%      &=\sum_{0\le m\le k}\frac{n^{m+1}}{m+1}{\binom{k+1}m}\sum_{m\le
%p\le k}{\binom{k+1-m}{p-m}}B_{p-m}+(k+1)\Delta\\
%      &=\sum_{0\le m\le k}\frac{n^{m+1}}{m+1}{\binom{k+1}m}\sum_{0\le
%p\le k-m}{\binom{k+1-m}p}B_p+(k+1)\Delta\\
%       &\text{ (just by definition: see (2))}\\
%     &=\sum_{0\le m \le k,
%k-m=0}\frac{n^{m+1}}{m+1}{\binom{k+1}m}+(k+1)\Delta=n^{k+1}+(k+1)\Delta.
%\end{align*}
%This calculation implies that $\Delta=0$.
%\newpage

\z This immediately
follows from the definition of the Bernoulli numbers. 
Let us illustrate how powerful the method of generating functions is.
Let $$\frac{\displaystyle t}{\displaystyle e^t-1}=\sum_{k\ge0}
\frac{\displaystyle{\widehat B}_kt^k}{\displaystyle k!}.$$
Then it is clear that 
$$
t=\sum_{k\ge0}\frac{\displaystyle t^{k+1}}{(k+1)!}\sum_{l\ge0}
\frac{\displaystyle{\widehat B}_lt^l}{\displaystyle l!}=
\sum_{k\ge0}\left(\sum_{i=0}^{k}{\binom{k+1}i}{\widehat B}_i\right)
\frac{\displaystyle t^{k+1}}{\displaystyle(k+1)!},
$$
so ${\widehat B}_k$ and $B_k$ satisfy the same recurrence relation
and initial condition and thus coincide. The rest of the proof is very simple:
the exponential generating function 
for the power
sums $S_k(n)$ with fixed $n$ is $$\sum_{k=0}^{n-1}e^{kt}
=\frac{\displaystyle e^{nt}-1}
{\displaystyle e^t-1}=\frac{\displaystyle e^{nt}-1}{\displaystyle t}\cdot
\frac{\displaystyle t}{\displaystyle e^t-1}=\sum_{k\ge0}
\frac{\displaystyle n^{k+1}t^k}{\displaystyle k!}\sum_{l\ge0}
\frac{\displaystyle B_lt^l}{\displaystyle l!}=\sum_{k\ge0}
\left(\frac1{k+1}\sum_{i=0}^k{\binom {k+1}i}B_in^{k+1-i}\right)\frac{t^k}{k!}.$$  


\z
\begin{tabular}{c|cccccccccc}
$n$&0&1&2&3&4&5&6&7&8&9\\
\hline
$B_n$&1&$-\frac12$&$\frac16$&0&$\frac{-1}{30}$&0&$\frac1{42}$&0
&$\frac{-1}{30}$&0\\
\end{tabular}

\begin{tabular}{c|cccccccccccc}
$n$&10&11&12&13&14&15&16&17&18&19&20\\
\hline
$B_n$&$\frac{5}{66}$&0&$\frac{-691}{2730}$&0&$\frac76$&0&$-\frac{3617}{510}$&0&
$\frac{43867}{798}$&0&$-\frac{174611}{330}$\\
\end{tabular}

$$
5, 7, 691, 3617, 43867\,\,\,{\rm are\,\,\, prime},\,\,\,6=2\cdot3, \,\,\,
30=2\cdot3\cdot5,\,\,\, 42=2\cdot3\cdot7,\,\,\, 
66=2\cdot3\cdot11,\,\,\,2730=2\cdot3\cdot5\cdot7\cdot13,\,\,
$$
$$
510=2\cdot3\cdot5\cdot17,\,\,
798=2\cdot3\cdot7\cdot19,\,\,\,174611=283\cdot617,\,\,\,330=2\cdot3\cdot5\cdot11.
$$

\z
(This solution was suggested by E.~Ferens--Sorotskij, O.~Styrt and O.~Evtifeeva
during the conference; I did not know it before. Other participants 
checked that the function $f(t)=\frac{\displaystyle t}{\displaystyle e^t-1}+
\frac{\displaystyle t}{\displaystyle 2}$ is even, but the correct explanation meets
some difficulties$\dots$)

Let $k$ be the minimal odd number greater than 1 such that $B_k\ne0$.
$P_k(n)+n^k=P_k(n+1)=P_k(-n)$~--- see solution for {\bf 9(e)} for details.
This means that 
$$
\frac{1}{k+1}\sum_{i=0}^{k}{\binom{k+1}i}B_i(-n)^{k+1-i}=
\frac{1}{k+1}\sum_{i=0}^{k}{\binom{k+1}i}B_in^{k+1-i}+n^k.
$$
By our hypothesis, $B_3=B_5=\dots=B_{k-2}=0$, therefore almost all terms cancel
and we have $n^k+2B_1n^k+2B_kn=0$. Since $B_1=-\frac12$, we see that $B_k=0$.

\z
$$
P_1(x)=\frac12x^2-\frac12x,\,\,\,\,P_2(x)=\frac13x^3-\frac12x^2+\frac16x, \,\,\,\,
P_3(x)=\frac14x^4-\frac12x^3+\frac14x^2,\,\,\,\,P_4(x)=\frac15x^5-\frac12x^4+\frac13x^3-\frac1{30}x,
$$
$$
P_5(x)=\frac16x^6-\frac12x^5+\frac5{12}x^4-\frac1{12}x^2,\,\,\,
P_6(x)=\frac17x^7-\frac12x^6+\frac12x^5-\frac16x^3+\frac1{42}x,\,\,\,
P_7(x)=\frac18x^8-\frac12x^7+\frac7{12}x^6-\frac7{24}x^4+\frac1{12}x^2,
$$
$$
P_8(x)=\frac19x^9-\frac12x^8+\frac23x^7-\frac7{15}x^5+\frac29x^3-\frac1{30}x,\,\,\,
P_9(x)=\frac1{10}x^{10}-\frac12x^9+\frac34x^8-\frac7{10}x^6+\frac12x^4-\frac3{20}x^2,
$$
$$
P_{10}(x)=\frac1{11}x^{11}-\frac12x^{10}+\frac56x^9-x^7+x^5-\frac12x^3+
\frac5{66}x,\,\,\,
P_{11}(x)=\frac1{12}x^{12}-\frac12x^{11}+\frac{11}{12}x^{10}-\frac{11}8x^8+
\frac{11}6x^6-\frac{11}8x^4+\frac5{12}x^2,
$$
$$
P_{12}(x)=\frac1{13}x^{13}-\frac12x^{12}+x^{11}-\frac{11}6x^9+\frac{22}7x^7-
\frac{33}{10}x^5+\frac53x^3-\frac{691}{2730}x,
$$
$$
P_{13}(x)=\frac1{14}x^{14}-\frac12x^{13}+\frac{13}{12}x^{12}-
\frac{143}{60}x^{10}+\frac{143}{28}x^8-\frac{143}{20}x^6
+\frac{65}{12}x^4-\frac{691}{420}x^2,
$$
$$
P_{14}(x)=\frac1{15}x^{15}-\frac12x^{14}+\frac76x^{13}-\frac{91}{30}x^{11}+
\frac{143}{18}x^9-\frac{143}{10}x^7+\frac{91}6x^5
-\frac{691}{90}x^3+\frac76x,
$$
$$
P_{15}(x)=\frac1{16}x^{16}-\frac12x^{15}+\frac54x^{14}-\frac{91}{24}x^{12}+
\frac{143}{12}x^{10}-\frac{429}{16}x^8+
\frac{455}{12}x^6-\frac{691}{24}x^4+\frac{35}4x^2,
$$
$$
P_{16}(x)=\frac1{17}x^{17}-\frac12x^{16}+\frac43x^{15}-\frac{14}3x^{13}+
\frac{52}3x^{11}-\frac{143}3x^9+\frac{260}3x^7-
\frac{1382}{15}x^5+\frac{140}3x^3-\frac{3617}{510}x,
$$
$$
P_{17}(x)=\frac1{18}x^{18}-\frac12x^{17}+\frac{17}{12}x^{16}-\frac{17}3x^{14}
+\frac{221}9x^{12}-\frac{2431}{30}x^{10}+\frac{1105}{6}x^8
-\frac{11747}{45}x^6+\frac{595}3x^4-\frac{3617}{60}x^2,
$$
$$
P_{18}(x)=\frac1{19}x^{19}-\frac12x^{18}+\frac32x^{17}-\frac{34}5x^{15}+
34x^{13}-\frac{663}5x^{11}+\frac{1105}3x^9-\frac{23494}{35}x^7
+714x^5-\frac{3617}{10}x^3+\frac{43867}{798}x,
$$

\begin{multline*}
P_{19}(x)=\frac1{20}x^{20}-\frac12x^{19}+\frac{19}{12}x^{18}-
\frac{323}{40}x^{16}+\frac{323}7x^{14}-\frac{4199}{20}x^{12}+\\
+\frac{4199}6x^{10}-\frac{223193}{140}x^8+2261x^6-\frac{68723}{40}x^4+
\frac{43867}{84}x^2
\end{multline*}
%\end{center}

\z
\p $6P_1(x)P_2(x)=5P_4(x)+P_2(x)$

\p $3P_2(x)P_2(x)=2P_5(x)+P_3(x)$

\p $12P_2(x)P_3(x)=7P_6(x)+5P_4(x)$

\p $2P_3(x)P_3(x)=P_7(x)+P_5(x)$


\p is obvious: denote by $\alpha$ the leading coefficient of the given
polynomial $P(x)$ of degree $k$ and apply the inductive hypothesis to the
polynomial ${\widehat P}(x):=P(x)-\alpha P_{k-1}(x)$ (of degree $k-1$).

\p\label{b}
(This proof is, as far as I know, due to L.Positselskij. Recently I
found out that the collection of formulae for $P_k(x)$ in~\cite{Lin}
leads to another variant of the following lemma.)

Define an operation $T$ on polynomials by
$(TP)(x):=P(1-x)$. Assign $P_0(x)=x-\frac12$ (!!).
\begin{Lemm}
$(TP_k)(x)=(-1)^{k+1}P_k(x)$ for all $k$.
\end{Lemm}

\begin{proof}
It is obvious for $k=0$. Assume that $k>0$.
Recall that $P_k(x+1)-P_k(x)=x^k$, $P_k(1)=0$ (see the solution
for~\ref{a}),
$P_k(0)=0$ (use explicit formula (1)).
This means that $(-1)^{k+1}P_k(-(-x))-(-1)^{k+1}P_k(1-(-x))=(-x)^k$, i.e.,
($y:=-x$) $y^k=(-1)^{k+1}P_k(-y)-(-1)^{k+1}P_k(1-y)=(TP_k)(y+1)-(TP_k)(y)$.
$(TP_k)(1)=0$ because $P_k$ vanishes at zero, hence the uniqueness of
$P_k$ concludes the proof.
\end{proof}

The rest of the proof shows the power of linear algebra.
It is clear that $T(P_kP_l)=T(P_k)T(P_l)=(-1)^{k+l}P_kP_l$.
Let $P_k(x)P_l(x)$ (a polynomial of degree $k+l+2$) have the following
expansion in $P_j$'s: $P_k(x)P_l(x)=\sum\limits_{j=0}^{k+l+1}b_jP_j(x)$. It
follows that $\sum\limits_{j=0}^{k+l+1}
(-1)^{k+l+1}b_jP_j(x)=(-1)^{k+l}P_k(x)P_l(x)=
T(P_kP_l)(x)=\sum\limits_{j=0}^{k+l+1}(-1)^{j+1}b_jP_j(x)$ and since such an
expansion is unique we see that $b_j$ must vanish for
$j\not\equiv k+l+1(2)$.

\p
$60P_3(x)P_4(x)=27P_8(x)+35P_6(x)-2P_4(x)$.

\z
Let us introduce the notation: $a\equiv b(k)$ means that $a-b$ is
divisible by $k$. (Most concentrated readers noticed this notation
above$\dots$)

\p Recall the Fundamental Theorem of Arithmetic
(speaking more precisely, this statement is equivalent to the traditional
form of FTA): if integers $a, b\not\equiv 0(p)$ then $ab\not\equiv 0(p)$.
This implies that multiplication by a non-zero remainder modulo $p$
is injective (i.e., maps different remainders into different ones).
Therefore it is obvious that for each non-zero remainder $a$ there exists (a
unique) remainder $b$ such that $ab-1\equiv0(p)$ (there are only
finitely many remainders, so the above means that each of them will occur).

\p
One may use the hint in order to prove the second statement. Let us deal
with the first one. For each $a$ not divisible by $p$ the
remainders of $a, 2a,\dots,(p-1)a$ form the complete system of non-zero
remainders modulo $p$. Hence $1\cdot2\cdots(p-1)(a^{p-1}-1)=
a\cdot2a\cdots(p-1)a-1\cdot2\cdots(p-1)\equiv0(p)$. 
Cancel $(p-1)!$ (it is relatively prime to $p$) to conclude the proof.

\z\p is a straightforward corollary of the above statement: $a^{l(p-1)}-1$
is divisible by $a^{p-1}-1\equiv0(p)\dots$

\p Consider the remainder ${\widehat k}$ of $k$ modulo $p-1$. Then
$a^k-a^{\widehat k}\equiv0(p)$ for all $a$ (it is obvious), so let us
show that $S_{\widehat k}(p)\equiv0(p)$. Let
$b$ be a non-zero remainder such that $b^{\widehat k}-1\not\equiv0(p)$.
Examine $b^{\widehat k}S_{\widehat k}(p)$. Since $b, 2b, \dots (p-1)b$
form the complete system of non-zero remainders, we see that $b^{\widehat
k}S_{\widehat k}(p)-S_{\widehat k}(p)\equiv0(p)$.
To conclude the proof, proceed as above.

{\bf Definition. }Let $p$ be a prime. Let us call a rational number a 
$p$-integer if its denominator is not divisible by $p$.

\z
(Here we follow~\cite{NTh}.)
Setting $n=p^r$ in $(1)$, we see that
$$  
\frac{S_{2k}(p^r)}{p^r}-B_{2k}=\frac1{2k+1}\sum_{j=0}^{2k-1}{\binom{2k+1}j}B_j
p^{r(2k-j)}.
$$
If $r$ is large enough the right-hand side (and the left-hand side as
well) is a $p$-integer.
On the other hand for $m\ge 1$
$$
S_{2k}(p^{m+1})=\sum_{u=0}^{p^m-1}\sum_{v=0}^{p-1}(u+vp^m)^{2k}
\equiv p\sum_{u=0}^{p^m-1}u^{2k}+kp^m\sum_uu^{2k-1}\sum_vv\equiv
pS_{2k}(p^m)(p^{m+1}),
$$
and this implies that
$\frac{S_{2k}(p^{m+1})}{p^{m+1}}-\frac{S_{2k}(p_m)}{p^m}$ is
an integer. Thus $\frac{S_{2k}(p)}{p}-B_{2k}$ is a $p$-integer as well. One
may replace $S_{2k}(p)$ by $0$ for $2k\not\equiv0(p-1)$
and $S_{2k}(p)$ by $1$ for $2k\equiv0(p-1)$ to obtain the
following statement (which is just what we need):

For any prime number $q$ \,$B_{2k}+\sum\limits_p\frac1p$ is a $q$-integer
(here the summation is taken over primes $p$ such that $2k\equiv0(p-1)$). 

Hence this (rational) number is an integer.

\z One may check that $44\equiv0(p-1)$ for a prime $p$ $\Leftrightarrow$
$p\in\{2,3,23\}$. Hence the denominator of $B_{22}$ is 138 and
$B_{22}+\frac12+\frac13+\frac1{23}$
is an integer $\Rightarrow
B_{22}=6193-\frac12-\frac13-\frac1{23}=6193-\frac{121}{138}
=\frac{854513}{138}$.

\z
Most of the participants used here the followig version of the
Dirichlet theorem: there is infinitely many primes having remainder
1 modulo 3. It was an interesting experience for me to hear different 
proofs of
this fact: for example, A.~Entin and D.~Faifman used the quadratic 
reciprocity law in order to prove it. Still I prefer solutions 
which avoid such strong machinery$\dots$
 
{\it First solution. } 

Suppose that for any prime $p$ such that $n$ is
divisible 
by $p$ $p$ is congruent to 1 modulo 6 (for example, take
$n=7,\,7^2,\,7^3\dots$). Let $q\ne2,3$ be a prime divisor of $B_{2n}$'s 
denominator. It
follows that $q\equiv\pm1(6)$, so $q-1$ is divisible either by $6$ or by
an integer $m\equiv-1(3)$. Both cases together with the equivalence
$2n\equiv0(q-1)$ and the assumption about prime divisors of $n$ lead
to contradiction which concludes the proof.

{\it Second solution. }

(It was known to me before, but I was glad 
to see it in the text submitted by E.~Ferens--Sorotskij, O.~Styrt
and O.~Evtifeeva.)
 
For a prime $p$ all divisors of $2p$ are $1, 2, p,
2p$, so
the denominator of $B_{2p}$ is equal to $6$ unless $2p+1$ is a prime
number. Otherwise try $p:=2p+1{\rm\,\, (and\,\, }2p+1:=4p+3{\rm)}$
etc. (There
{\it will} occur a composite number:
for example, $2^{p-1}p+2^{p-1}-1$ is divisible by $p\dots$)
 
%\begin{thebibliography}{XXXX}
%\bibitem[BSh]{NTh} 
%Z.~I.~Borevich, I.~R.~Shafarevich. Number theory.
%(In Russian: Moscow, Nauka Publishers, 1985.)
%\bibitem[G]{FD} A.~O.~Gel'fond. Calculus of finite differences.
%(In Russian: Moscow-Leningrad, GITTL, 1952.)
%\bibitem[GKP]{CM} R.~L.~Graham, D.~E.~Knuth, O.~Patashnik. Concrete
%mathematics. (In Russian: Moscow, Mir Publishers, 1998.)
%\bibitem[MS]{CC} J.~W.~Milnor, J.~D.~Stasheff. Characteristic classes.
%(In Russian: Volgograd, Platon Publishers, 1998.)
%\bibitem[Pr]{Lin} V.~V.~Prasolov. Problems and theorems of linear
%algebra. (In Russian: Moscow, Nauka Publishers, 1996.)
%\end{thebibliography}


%\z\p\p 
%Use hints or~\cite{CC}.

%\z Let $p$ be a prime. If the denominator of $B_{2n}$ is divisible by $p$
%then so is the denominator of $B_{2n}/n$ as well. Assume that
%$B_{2n}$ is a $p$-integer. Then $2n\not\equiv0(p-1)$ so
%there exists $b\not\equiv0(p)$ such that $b^{2n}-1\not\equiv0(p)$. Hence
%we have an integer number $b^{2n}(b^{2n}-1)/2$ which is relatively prime
%to $p$, and $B_{2n}/n=\frac{{\rm
%an\,\,integer}}{b^{2n}(b^{2n}-1)/2}$,
%and so $B_{2n}/n$ is a $p$-integer.
%\newpage
 
\z\p\p Let us follow the solutions suggested by
A.~Entin \& D.~Faifman, O.Golberg, M.~Levin (compare this to the
one in~\cite{CC}, which involves generating functions). The idea is to 
draw on the result of {\bf 16}: 
we will show that for each prime $p$ the number 
$a^{2n}(a^{2n}-1)B_{2n}/2n$
is a $p$-integer. It is obvious for $p$ such that $2n$ is not divisible 
by $p-1$ (use {\bf 12} and {\bf 16}). Suppose that $2n$ is divisible by
$p-1$; $2n=(p-1)p^km$, where 
$m$ is not divisible by $p$. For $a$ divisible by $p$ its power
$a^{2n}$ is divisible by $p^{2n}$ (it is divisible by $p^{k+1}$
because $2n\ge p^k\ge k+1$, and the denominator of $B_{2n}/2n$
is divisible by exactly $p^{k+1}$~--- see {\bf 12}). For $a$ not
divisible by $p$ the number $a^{2n}-1$ is divisible by $p^{k+1}$ because 
$2n$ is divisible by $p^{k+1}-p^k=\varphi(p^{k+1})$. (Here we use 
Euler's theorem: for $a$ relatively prime to $n$ there holds
an equivalence $a^{\varphi(n)}\equiv1(n)$,
where $\varphi(n)$ denotes the number of integers less than $n$ and
relatively prime to $n$. The proof is similar to the proof of {\bf 10(b)}.) 

\z (This solution was suggested by A.~Entin \& D.~Faifman. The main 
advantage of this approach is that one may easily rewrite it for {\bf 17}.
O.~Golberg and
M.~Levin used the existence of a primitive root modulo $p^k$ (for $p\ne2$);
E.~Ferens--Sorotskii, O.~Styrt and O.~Evtifeeva deduced it from {\bf 15},
which was deduced from a very complicated solution of {\bf 17}.)

Let $1\le g\le p-1$ be such that $g^k-1$ is not divisible by
$p$ for $0<k<p-1$(\«ª $g$ is a primitive root modulo $p$\¯ª. 
{\bf Exercise.} Prove that
there exists such a $g$~--- it is not very difficult.)
$$
\frac{\displaystyle gt}{\displaystyle e^{gt}-1}-
\frac{\displaystyle t}{\displaystyle e^t-1}
=\sum_{k\ge1}(g^k-1)B_k\frac{\displaystyle t^k}{\displaystyle k!}=
t\sum_{k\ge1}G_k\frac{\displaystyle t^{k-1}}{\displaystyle (k-1)!},
$$ 
where $G_k=(g^k-1)\frac{\displaystyle B_k }{\displaystyle k}$.
$
\sum\limits_{k\ge1}G_k\frac{\displaystyle t^{k-1}}{\displaystyle (k-1)! }=
\frac{\displaystyle g }{\displaystyle e^{gt}-1 }-
\frac{\displaystyle 1}{\displaystyle e^t-1}.
$

Denote $e^t-1$ by $u$.
$$
\frac{\displaystyle g }{\displaystyle e^{gt}-1 }-
\frac{\displaystyle 1}{\displaystyle e^t-1}=
\frac{\displaystyle g }{\displaystyle (1+u)^{g}-1 }-
\frac{\displaystyle 1}{\displaystyle u}=
\frac{\displaystyle g }{\displaystyle gu+\sum_{j=2}^gc_ju^j}-
\frac{\displaystyle 1}{\displaystyle u}=
\frac1u\left(\frac{\displaystyle 1}{\displaystyle 1+\sum_{j=2}^{g}c_ju^{j-1}/g}-1
 \right).
$$
Let us notice that 
$$
\frac{\displaystyle 1}{\displaystyle 1+
\sum_{j=2}^{g}c_ju^{j-1}/g}=1+\sum_{j\le1}d_ju^j,
$$
where the denominators of $d_j$ are not divisible by $p$.
Therefore 
$$
\sum_{k\ge1}G_k
\frac{\displaystyle t^{k-1}}{\displaystyle (k-1)!}=
\sum_{r\ge0}a_r(e^t-1)^r=\sum_{r\ge0}a_r\sum_{m=0}^{r}(-1)^{r-m}{\binom r m}e^{mt},
$$
where all $a_r$ are $p$-integers.
Replacing all $e^{mt}$ by the corresponding power series gives us
$$
G_k=x_1+x_2\cdot2^{k-1}+\dots x_k\cdot(k-1)^{k-1},
$$
where $x_k$ are $p$-integers.
(Here we use the fact that the power series expansion 
for $(e^t-1)^m$ starts from $t^m$.)
Therefore $G_k$ is a $p$-integer for all $k$. 
Let us return to the solution. $B_{2n}/n$ is a $p$-integer $\Rightarrow$
$B_{2n}$ is a $p$-integer (it is obvious). Suppose that $B_{2n}$ is a
$p$-integer. This means that $2n$ is not divisible by $p-1$, so 
$g^{2n}-1$ is not divisible by $p$ and thus $B_{2n}/n$ is a $p$-integer.

\z
(Most of the work was done in the above solution for {\bf 16}.)
Write $$
G_{2k}=\sum_{m=1}^{2k+p-2}x_mm^{2k-1},
$$
where $x_m$ are $p$-integers (expand the sum $\sum\limits_{r=0}^{2k+p-2}
a_r(e^t-1)^r$.).
Then it is clear that 
$$
G_{2k+p-1}=\sum{m=1}^{2k+p-2}x_mm^{2k+p-2}
$$
(the proof is similar to the one above).
Thus 
$$
G_{2k+p-1}-G_{2k}=\sum_{m=1}^{2k+p-2}x_mm^{2k-1}(m^{p-1}-1),
$$
so its numerator is divisible by $p$.
$$
G_{2k+p-1}-G_{2k}=g^{2k}(g^{p-1}-1)
\frac{\displaystyle B_{2k+p-1}}{\displaystyle 2k+p-1}+
(g^{2k}-1)
(\frac{\displaystyle B_{2k+p-1}}{\displaystyle 2k+p-1}-
\frac{\displaystyle B_{2k}}{\displaystyle 2k}),
$$
and since the numerator of 
$g^{2k}(g^{p-1}-1)\frac{\displaystyle B_{2k+p-1}}{\displaystyle 
2k+p-1}$ is divisible by $p$ (use {\bf 10} and {\bf 12}) and
$g^{2k}-1$ is not divisible by $p$ ($2k$ is not divisible by $p-1$),
we see that the numerator of  
$(
\frac{\displaystyle B_{2k+p-1}}{\displaystyle 2k+p-1}-\frac{\displaystyle B_{2k}}
{\displaystyle 2k})$ is divisible by $p$.
Now one may obtain Kummer's congruence simply by induction.

\z
Suppose that there are only finitely many irregular primes: $p_1,\,\dots,p_k$.
Choose an integer $n$ large enough to have 
$\left|\frac{\displaystyle B_{2m}}{\displaystyle 2m}\right|>1$ ($m=n(p_1-1)\cdots
(p_k-1)$). It is clear that the denominator of 
$\frac{\displaystyle B_{2m}}{\displaystyle 2m}$ is divisible by $p_i$ for
all $i=1,\dots,k$ (use {\bf 12} and {\bf 16}), so its numerator is equal to
$\pm1$ (by our hypothesis, if it is divisible by a prime $p$, then $p$ is
one of $p_i$'s). 
This contradicts $\left|\frac{\displaystyle B_{2m}}{\displaystyle 2m}\right|>1$.

\z
Denote this constant term by $C(a_1,\dots,a_k)$. Let us show that 
$C(a_1,\dots,a_k)=C(a_1-1,a_2,\dots,a_k)+\dots+C(a_1,\cdots,a_k-1)$ 
(there are obvious initial conditions 
$C(a_1,\dots,a_{k-1},0)=C(a_1,\dots,a_{k-1})$ and $C(0)=1$). Since multinomial
coefficients satisfy the same recurrence relation and initial condition,
the Dyson's conjecture follows.
The proof is very simple:
%we will show that 
%$$
%\sum_{j=1}^n\prod_{i\ne j}\frac{\displaystyle 1}{\displaystyle 
%1-\frac{\displaystyle x_j}{\displaystyle x_i}}=
%\sum_{j=1}^n\prod_{i\ne j}\frac{\displaystyle x_i}{\displaystyle x_i-x_j}=1.
%$$
%Indeed, 
consider the polynomial 
$f(x)=\sum\limits_{j=1}^n\prod\limits_{i\ne j}\frac{\displaystyle x_i-x}
{\displaystyle x_i-x_j}$. Its degree is $n-1$ and $f(x_1)=\dots=f(x_n)=1$,
so $f(x)\equiv1$. 
Thus $$1=f(0)=\sum_{j=1}^n\prod_{i\ne j}\frac{\displaystyle x_i}
{\displaystyle x_i-x_j}=\sum_{j=1}^n\prod_{i\ne j}\frac{\displaystyle 1}{\displaystyle 
1-\frac{\displaystyle x_j}{\displaystyle x_i}}.
$$ 
Multiply 
$
\prod\limits_{1\le i\ne j\le n}\left(1-\frac{\displaystyle x_j}
{\displaystyle x_i}\right)^{a_j}
$
by this equality to obtain the above 
recurrence relation.

{\phantom{\z}} 

\z Hint: check that the sequences 
$y_{i}(n):=\sum\limits_{k\equiv i(p-1)}{\binom{2n+1}k}$ have
periods modulo $p$ for all $i=0,\dots p-2$.

\z Hint: this recurrence relation means that the exponential generating
function for the Bernoulli numbers satisfies a certain differential 
equation (write out this equation!).

\z This is simply a straightforward calculation.

\z Adding up the equalities from the previous problem, we obtain
$$
\sum_{0<2j<2k}\zeta(2i)\zeta(2k-2i)=\sum_{m,n}f(m,n)-\sum_{m>n}f(m,n)-
\sum_{m<n}f(m,n)=\sum_{n}f(n,n)=\frac{2k+1}2\zeta(2k).
$$
Use the recurence relation from {\bf 22} to obtain (simply by induction)
 the classical result
$$
\zeta(2k)=(-1)^{k-1}2^{2k-1}B_{2k}\frac{\displaystyle \pi^{2k}}
{\displaystyle (2k)!}.
$$

\begin{thebibliography}{XXXX}
\bibitem[BSh]{NTh} 
Z.~I.~Borevich, I.~R.~Shafarevich. Number theory.
(In Russian: Moscow, Nauka Publishers, 1985.)
\bibitem[G]{FD} A.~O.~Gel'fond. Calculus of finite differences.
(In Russian: Moscow-Leningrad, GITTL, 1952.)
\bibitem[GKP]{CM} R.~L.~Graham, D.~E.~Knuth, O.~Patashnik. Concrete
mathematics. (In Russian: Moscow, Mir Publishers, 1998.)
\bibitem[MS]{CC} J.~W.~Milnor, J.~D.~Stasheff. Characteristic classes.
(In Russian: Volgograd, Platon Publishers, 1998.)
\bibitem[Pr]{Lin} V.~V.~Prasolov. Problems and theorems of linear
algebra. (In Russian: Moscow, Nauka Publishers, 1996.)
\end{thebibliography}

\end{document}
