Summary: We prove that congruences modulo \(p\) 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 refine the Brauer-Nesbitt theorem for a single linear operator, motivated by the study of Hecke modules of modular forms modulo \(p\).