Some properties of $p(n)$, the number of partitions of $n$1
Proceedings of the Cambridge Philosophical Society, XIX, 1919, 207 – 210

1. A recent paper by Mr Hardy and myself2 contains a table, calculated by Major MacMahon, of the values of $p(n)$, the number of unrestricted partitions of $n$, for all values of $n$ from 1 to 200. On studying the numbers in this table I observed a number of curious congruence properties, apparently satisfied by $p(n)$. Thus

$$\begin{array}{rllllllll} (1) & p(4), & p(9), & p(14), & p(19), & \cdots & \equiv 0\pmod{ 5}, \\ (2) & p(5), & p(12), & p(19), & p(26), & \cdots & \equiv 0\pmod{ 7}, \\ (3) & p(6), & p(17), & p(28), & p(39), & \cdots & \equiv 0\pmod{ 11},\\ (4) & p(24), & p(49), & p(74), & p(99), & \cdots & \equiv 0\pmod{ 25},\\ (5) & p(19), & p(54), & p(89), & p(124),& \cdots & \equiv 0\pmod{35},\\ (6) & p(47), & p(96), & p(145),& p(194),& \cdots & \equiv 0\pmod{49},\\ (7) & p(39), & p(94), & p(149),& \cdots & & \equiv 0\pmod{55},\\ (8) & p(61), & p(138),& \cdots & & & \equiv 0\pmod{77},\\ (9) & p(116),& \cdots & & & & \equiv 0\pmod{ 121},\\ (10)& p(99), & \cdots & & & & \equiv 0\pmod{ 125}.\\ \end{array}$$

From these data I conjectured the truth of the following theorem: if $\delta= 5^a 7^b 11^c$ and $24 \lambda \equiv 1 \pmod{\delta}$ then $$p(\lambda),\: p(\lambda + \delta), \: p(\lambda + 2 \delta), \cdots \equiv 0\pmod{\delta}.$$ This theorem is supported by all the available evidence; but I have not yet been able to find a general proof.

I have, however, found quite simple proofs of the theorems expressed by (1) and (2), viz.

\begin{equation*} p(5m+4) \equiv 0\pmod{5}\tag{1} \end{equation*}
and
\begin{equation*} p(7m+5) \equiv 0\pmod{7}.\tag{2} \end{equation*}
From these
\begin{equation*} p(35m + 19) \equiv 0\pmod{35} \tag{5} \end{equation*}
follows at once as a corollary. These proofs I give in § 2 and § 3. I can also prove
\begin{equation*} p(25n + 24) \equiv 0\pmod{25} \tag{4} \end{equation*}
and
\begin{equation*} p(49n + 47) \equiv 0\pmod{49}, \tag*{(6),} \end{equation*}
but only in a more recondite way, which I sketch in § 4.

2. Proof of (1). We have

\begin{align*} x\{(1-x)(1-x^2) (1-x^3)\cdots\}^4 & = x(1-3x+5x^3-7x^6+\cdots)(1-x-x^2+x^5+\cdots)\\ & = \sum (-1)^{\mu+\nu} (2\mu +1) x^{1+\frac{1}{2}\mu(\mu+1)+\frac{1}{2}\nu(3\nu+1)},\tag{11} \end{align*}
the summation extending from $\mu=0$ to $\mu=\infty$ and from $\nu =-\infty$ to $\nu=\infty$.

Now if $$1 + \half \mu (\mu + 1) + \half \nu (3 \nu+1) \equiv 0\pmod{5},$$ then $$8 + 4\mu(\mu+1) + 4\nu(3\nu+1) \equiv 0\pmod{5},$$ and therefore

\begin{equation*} (2 \mu + 1)^2+ 2(\nu+1)^2 \equiv 0\pmod{5}. \tag{12} \end{equation*}
But $(2\mu+1)^2$ is congruent to 0,1 or 4, and $2(\nu+1)^2$ to 0, 2, or 3. Hence it follows from (12) that $2 \mu+1$ and $\nu+1$ are both multiplies of 5. That is to say, the coefficient of $x^{5n}$ in (11) is a multiple of 5.

Again, all the coefficients in $(1-x)^{-5}$ are multiples of 5, except those of $1, x^5, x^{10}, \ldots,$ which are congruent to 1: that is to say $$\frac{1}{(1-x)^5} \equiv \frac{1}{1-x^5} \pmod{5},$$ or $$\frac{1-x^5}{(1-x)^5} \equiv 1\pmod{5}.$$ Thus all the coefficients in $$\frac{(1-x^5)(1-x^{10})(1-x^{15})\cdots}{\{(1-x)(1-x^2)(1-x^3)\cdots\}^5}$$ (except the first) are multiples of 5. Hence the coefficient of $x^{5n}$ in $$\frac{x(1-x^5)(1-x^{10})\cdots}{(1-x)(1-x^2)(1-x^3)\cdots} = x \{(1-x)(1-x^2)\cdots\}^4 \frac{(1-x^5)(1-x^{10})\cdots} {\{(1-x)(1-x^2)\cdots\}^5}$$ is a multiple of 5. And hence, finally, the coefficient of $x^{5n}$ in $$\frac{x}{(1-x)(1-x^2)(1-x^3)\cdots}$$ is a multiple of 5; which proves (1).

3. Proof of (2). The proof of (2) is very similar. We have

\begin{align*} x^2\{(1-x)(1-x^2)(1-x^3)\cdots\}^6 &= x^2(1-3x+5x^3-7x^6+ \cdots)^2 \\ &= \sum(-1)^{\mu+\nu} (2\mu+1)(2\nu+1) x^{2+\frac{1}{2}\mu(\mu+1)+\frac{1}{2}\nu(\nu+1)},\tag{13} \end{align*}
the summation now extending from 0 to $\infty$ for both $\mu$ and $\nu$. If $$2 + \half \mu (\mu+1) + \half \nu (\nu+1) \equiv 0\pmod{7},$$ then $$16 + 4\mu(\mu+1) + 4\nu(\nu+1) \equiv\pmod{7},$$ $$(2\mu+1)^2 + (2\nu+1)^2 \equiv 0\pmod{7},$$ and $2 \mu + 1$ and $2 \nu+1$ are both divisible by 7. Thus the coefficient of $x^{7n}$ in (13) is divisible by 49.

Again, all the coefficients in $$\frac{(1-x^7)(1-x^{14})(1-x^{21})\cdots} {\{(1-x)(1-x^2)(1-x^3)\cdots\}^7}$$ (except the first) are multiples of 7. Hence (arguing as in § 2) we see that the coefficient of $x^{7n}$ in $$\frac{x^2}{(1-x)(1-x^2)(1-x^3)\cdots}$$ is a multiple of 7; which proves (2). As I have already pointed out, (5) is a corollary.

4. The proofs of (4) and (6) are more intricate, and in order to give them I have to consider a much more difficult problem. viz. that of expressing $$p(\lambda) + p(\lambda+\delta) x + p(\lambda + 2\delta) x^2 + \cdots$$ in terms of Theta-functions, in such a manner as to exhibit explicitly the common factors of the coefficients, if such common factors exist. I shall content myself with sketching the method of proof, reserving any detailed discussion of it for another paper.

It can be shewn that

\begin{align*} & \frac{(1-x^5)(1-x^{10})(1-x^{15})\cdots}{(1-x^{\frac{1}{5}}) (1-x^{\frac{2}{5}})(1-x^{\frac{3}{5}})\cdots} = \frac{1}{\xi^{-1} - x^{\frac{1}{5}} - \xi x^{\frac{2}{5}}} \\ &= \frac{\xi^{-4} - 3 x\xi + x^{\frac{1}{5}} (\xi^{-3} + 2x\xi^2) + x^{\frac{2}{5}} (2\xi^{-2} - x\xi^3) + x^{\frac{3}{5}}(3\xi^{-1} + x\xi^4) + 5x^{\frac{4}{5}}}{\xi^{-5} - 11x - x^2\xi^5},\tag{14} \end{align*}
where $$\xi = \frac{(1-x)(1-x^4)(1-x^6)(1-x^9)\cdots}{(1-x^2)(1-x^3)(1-x^7)(1-x^8)\cdots},$$ the indices of the powers of $x$, in both numerator and denominator of $\xi$, forming two arithmetical progressions with common difference 5. It follows that
\begin{equation*} (1-x^5)(1-x^{10})(1-x^{15}) \cdots \{p(4)+p(9) x+p(14)x^2+\cdots\} = \frac{5}{\xi^{-5} - 11x - x^2\xi^5}. \tag{15} \end{equation*}
Again, if in (14) we substitute $\omega x^{\frac{1}{5}}, \omega^2x^{\frac{1}{5}}, \omega^3x^{\frac{1}{5}}$, and $\omega^4x^{\frac{1}{5}}$, where $\omega^5=1$, for $x^{\frac{1}{5}}$, and multiply the resulting five equations, we obtain
\begin{equation*} \left\{\frac{(1-x^5)(1-x^{10})(1-x^{15}) \cdots}{(1-x)(1-x^2)(1-x^3)\cdots}\right\}^6 = \frac{1}{\xi^{-5}-11x - x^2\xi^5}.\tag{16} \end{equation*}
From (15) and (16) we deduce
\begin{equation*} p(4) + p(9)x + p(14) x^2 + \cdots = 5\frac{\{(1-x^5)(1-x^{10})(1-x^{15})\cdots\}^5} {\{(1-x)(1-x^2)(1-x^3)\cdots\}^6}; \tag{17} \end{equation*}
from which it appears directly that $p(5m+4)$ is divisible by 5.

The corresponding formula involving 7 is

\begin{align*} & p(5) + p(12) x + p(19) x^2 + \cdots\\ &\quad = 7 \frac{\{(1-x^7)(1-x^{14})(1-x^{21})\cdots\}^3} {\{(1-x)(1-x^2)(1-x^3)\cdots\}^4} +49x \frac{\{(1-x^7)(1-x^{14})(1-x^{21})\cdots\}^7} {\{(1-x)(1-x^2)(1-x^3)\cdots\}^8},\tag{18} \end{align*}
which shews that $p(7m+5)$ is divisible by 7.

From (16) it follows that $$\frac{p(4)x+p(9) x^2+p(14)x^3+\cdots} {5\{(1-x^5)(1-x^{10})(1-x^{15})\cdots\}^4} = \frac{x}{(1-x)(1-x^2)(1-x^3)\cdots} \frac{\{(1-x^5)(1-x^{10})(1-x^{15})\cdots}{\{(1-x)(1-x^2)(1-x^3)\cdots\}^5} .$$ As the coefficient of $x^{5n}$ on the right-hand side is a multiple of 5, it follows that $p(25m + 24)$ is divisible by 25.

Similarly \begin{align*} & \frac{p(5)x+p(12) x^2+p(19)x^3+\cdots} {7\{(1-x^7)(1-x^{14})(1-x^{21})\cdots\}^2}\\ &\quad = x(1-3x + 5x^3 - 7x^6 +\cdots ) \frac{(1-x^7)(1-x^{14})\cdots}{\{(1-x)(1-x^2)\cdots\}^7} + 7x^2 \frac{\{(1-x^7)(1-x^{14})\cdots\}^5}{\{(1-x)(1-x^2)\cdots\}^8}; \end{align*} from which it follows that $p(49m + 47)$ is divisible by 49.

Another proof of (1) and (2) has been found by Mr. H. B. C. Darling, to whom my conjecture had been communicated by Major MacMahon. This proof will also be published in these Proceedings. I have since found proofs of (3), (7) and (8).

Endnotes

1[See also Ramanujan's posthumous paper Congruence properties of partitions'' in the Math. Zeitschrift, [No.30 of this volume].

2G. H. Hardy and S.Ramanujan, Asymptotic formulĂ¦ in Combinatory Analysis,'' Proc. London Math. Soc., Ser. 2, Vol. XVII, 1918, pp. 75 – 115 (Table IV, pp. 114 – 115) [No.36 of this volume].