  We prove that mod-$p$ congruences between polynomials in $\mathbb{Z}_p[X]$
are equivalent to deeper $p$-power congruences between power-sum functions of
their roots. This result generalizes to torsion-free
$\mathbb{Z}_{(p)}$-algebras modulo divided-power ideals. Our approach is
combinatorial: we introduce a $p$-equivalence relation on partitions, and use
it to prove that certain linear combinations of power-sum functions are
$p$-integral. We also include a second proof, short and algebraic, suggested by
an anonymous referee. As a corollary we obtain a refinement of the
Brauer-Nesbitt theorem for a single linear operator, motivated by the study of
Hecke modules of mod-$p$ modular forms.
