Let Bn(t) be the n-th
Bernoulli polynomial. We show that Bp−1(a∕q) − Bp−1≡ q(Up− 1)∕2p (modp),
where Un is a certain linear recurrence of order [q∕2] which depends only on a,q and
the least positive residue of p (modq). This can be re-written as a sum of linear
recurrence sequences of order ≤ ϕ(q)∕2, and so we can recover the classical results
where ϕ(q) ≤ 2 (for instance, Bp−1(1∕6) − Bp−1≡ (3p− 3)∕2p + (2p− 2)∕p(modp)). Our results provide the first advance on the question of evaluating
these polynomials when ϕ(q) > 2, a problem posed by Emma Lehmer in
1938.