Catalan and Apéry numbers in residue classes

We estimate character sums with Catalan numbers and middle binomial coefficients modulo a prime p. We use this bound to show that the first at most p 13 / 2 ( log p ) 6 elements of each sequence already fall in all residue classes modulo every sufficiently large p, which improves the previously known result requiring p O ( p ) elements. We also study, using a different technique, similar questions for sequences satisfying polynomial recurrence relations like the Apéry numbers. We show that such sequences form a finite additive basis modulo p for every sufficiently large prime p.