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 )⁶ 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.