  We develop a new method for proving algebraic independence of $G$-functions.
Our approach rests on the following observation: $G$-functions do not always
come with a single linear differential equation, but also sometimes with an
infinite family of linear difference equations associated with the Frobenius
that are obtained by reduction modulo prime ideals. When these linear
difference equations have order one, the coefficients of the $G$-function
satisfy congruences reminiscent of a classical theorem of Lucas on binomial
coefficients. We use this to derive a Kolchin-like algebraic independence
criterion. We show the relevance of this criterion by proving, using p-adic
tools, that many classical families of $G$-functions turn out to satisfy
congruences "\`a la Lucas".
