We introduce several new methods to obtain upper bounds on the number of solutions of the congruences f (x) ≡ y (mod p) and f (x) ≡ y 2 (mod p), with a prime p and a polynomial f , where (x, y) belongs to an arbitrary square with side length M. We give two applications of these results to counting hyperelliptic curves in isomorphism classes modulo p and to the diameter of partial trajectories of a polynomial dynamical system modulo p.