 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/ia/paper-4/6e/iii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-06

Write both nonnegative integers

n, k

in base-p expansions, padding with zero digits to a common length

L

. By the preceding polynomial identity,

(1 + x)^{n} = \prod_{i = 0}^{L} ((1 + x)^{p^{i}})^{n_{i}} \equiv \prod_{i = 0}^{L} (1 + x^{p^{i}})^{n_{i}} (mod p) .

Expanding the last product with the binomial theorem, each term is obtained by choosing an integer

j_{i}

with

0 \leq j_{i} \leq n_{i} < p

. Its exponent is

\sum_{i} j_{i} p^{i}

and its coefficient is

\prod_{i} (j _{i} n _{i})

. Uniqueness of base-p expansions says that the only way this exponent can equal

k

is to choose

j_{i} = k_{i}

for every

i

If some

k_{i} > n_{i}

, no such term exists and the coefficient is zero. Otherwise its coefficient is precisely the product below. Comparing the coefficient of

x^{k}

(k n) \equiv i = 0 \prod L (k _{i} n _{i}) (mod p),

with the convention

(b a) = 0

for

b > a

. This also covers

k > n

, and padding either expansion by further zero digits multiplies the product only by

(0 0) = 1

 New to topics? Read the docs here!