  Every polynomial $P(X)\in \mathbb Z[X]$ satisfies the congruences
$P(n+m)\equiv P(n) \mod m$ for all integers $n, m\ge 0$. An integer valued
sequence $(a_n)_{n\ge 0}$ is called a pseudo-polynomial when it satisfies these
congruences. Hall characterized pseudo-polynomials and proved that they are not
necessarily polynomials. A long standing conjecture of Ruzsa says that a
pseudo-polynomial $a_n$ is a polynomial as soon as $\limsup_n \vert
a_n\vert^{1/n}<e$. Under this growth assumption, Perelli and Zannier proved
that the generating series $\sum_{n=0}^\infty a_n z^n$ is a $G$-function. A
primary pseudo-polynomial is an integer valued sequence $(a_n)_{n\ge 0}$ such
that $a_{n+p}\equiv a_n \mod p$ for all integers $n\ge 0$ and all prime numbers
$p$. The same conjecture has been formulated for them, which implies Ruzsa's,
and this paper revolves around this conjecture. We obtain a Hall type
characterization of primary pseudo-polynomials and draw various consequences
from it. We give a new proof and generalize a result due to Zannier that any
primary pseudo-polynomial with an algebraic generating series is a polynomial.
This leads us to formulate a conjecture on diagonals of rational fractions and
primary pseudo-polynomials, which is related to classic conjectures of Christol
and van der Poorten. We make the Perelli-Zannier Theorem effective. We prove a
P\'olya type result: if there exists a function $F$ analytic in a right-half
plane with not too large exponential growth (in a precise sense) and such that
for all large $n$ the primary pseudo-polynomial $a_n=F(n)$, then $a_n$ is a
polynomial. Finally, we show how to construct a non-polynomial primary
pseudo-polynomial starting from any primary pseudo-polynomial generated by a
$G$-function different of $1/(1-x)$.

Number Theory