We study the dimensions of the eigenspaces for the Atkin-Lehner involutions acting on spaces of modular forms $M_k(\Gamma_0(Np))$, with the additional constraint imposed by fixing the mod $p$ Galois representation attached to the eigenforms. For this purpose we establish isomorphisms up to semisimplification between certain Hecke modules in characteristic $p$, generalizing Serre’s work relating modular forms mod $p$ to quaternion algebras. These isomorphisms are in turn obtained via a delicate study of congruences in the trace formulas for Hecke and Atkin-Lehner operators.