Simultaneous factorial valuations: how does pigeonhole give residue zero?

mimic_chest·Feb 3, 2025(edited)

Pigeonhole gives two equal vectors of factorial valuations modulo

d

, but subtracting their indices doesn't subtract factorial valuations. I don't see how to turn a repeated vector into the zero vector. Problem: For a prime

p

and a positive integer

n

, denote by

\nu_{p}(n)

the exponent of

p

in the prime factorization of

n!

. Given a positive integer

d

and a finite set

\{p_{1}, \ldots, p_{k}\}

of primes. Show that there are infinitely many positive integers

n

such that

d \mid \nu_{p_{i}}(n)

for all

1 \leq i \leq k

. Source: IMO 2007 Shortlist · MNET-06PU

Open MNET-06PU in the question bank →

6 replies

korok_delivery·Feb 3, 2025(edited)

You need an additive family of indices first. If

0\le r<p^t

, then

v_p((qp^t+r)!)=v_p((qp^t)!)+v_p(r!)

: for

1\le j\le r

v_p(qp^t+j)=v_p(j)

mimic_chest·Feb 3, 2025

That only works in a short interval after a large multiple. How do we arrange it for all the primes at once?

korok_delivery·Feb 4, 2025

Put

P=p_1\cdots p_k

N_1=1

, and

N_{j+1}=P^{N_j}

. If

i<j

, then each

p_\ell^{N_i}

divides

N_j

, while

N_i<p_\ell^{N_i}

slime_ranchero·Feb 4, 2025

Peel off the smallest index in any sum of distinct

N_j

's. The lemma shows the valuation vector of the factorial of that sum is the sum of the individual vectors modulo

d

. Repeat to get full additivity on these finite sums.

mimic_chest·Feb 4, 2025

Now infinitely many

N_j

have the same vector

v

. Choosing

d

of them makes the vector

dv=0

korok_delivery·Feb 6, 2025

Yes, and use successive disjoint blocks of

d

indices from that infinite subsequence. Their sums strictly increase, so you get infinitely many different positive integers, not just repeated witnesses.