Let's first consider Chern classes mod $p$ for an odd prime $p$, or if you like, $H^*(BU; \mathbb{Z}/p)$. Theorem 4 of the paper mod p Wu formulas for the Steenrod algebra and the Dyer-Lashof algebra by Brian Shay gives a formula for the Steenrod powers of Chern classes:
$$ P^{j-k}(c_j) = \sum (-1)^{\sum r_\gamma} \prod \frac{(-1)^{l_\alpha}}{l_\alpha} \left\{\frac{(j_\alpha - k_\alpha)p + k_\alpha}{j_\alpha} {j_\alpha \choose k_\alpha} \frac{1}{t_\alpha} {t_\alpha \choose t_{\alpha 1} \cdots t_{\alpha ((j_\alpha - k_\alpha)p + k_\alpha)}} \right\}^{l_\alpha} c_1^{r_1} c_2^{r_2} \cdots c_{(j - k)p + k}^{r_{(j - k)p + k}} $$
for "admissible summands": $\sum_\alpha k_\alpha l_\alpha = k$,
$\sum_\alpha j_\alpha l_\alpha = j$, $\sum_\gamma \gamma t_{\alpha \gamma}
= (j_\alpha - k_\alpha)p + k_\alpha$, $\sum_\alpha l_\alpha t_{\alpha \gamma} = r_\gamma$, $\sum_\gamma t_{\alpha\gamma} = t_\alpha$, $\sum_\gamma r_\gamma < p$, $j_\alpha > k_\alpha$ with at most one exception, for which $t_\alpha = l_\alpha = 1$, $k_\alpha > 0$ unless $k = 0$.
This is indeed not the nicest formula. However, we're only really interested in the coefficient of $c_{(j - k)p + k}$, and the only way to achieve that $r_\gamma = 1$ for $\gamma = (j - k)p + k$ and $r_\gamma = 0$ for all other values of $\gamma$ is to take $l_\alpha = 1$ for a single index $\alpha$, for which $k_\alpha = k$, $j_\alpha = j$, $t_{\alpha\gamma} = 1$ for $\gamma = (j - k)p + k$ and $t_{\alpha\gamma} = 0$ for other $\gamma$. The resulting coefficient is therefore
$$ \frac{(j-k)p + k}{k} {j \choose k} . $$
Rewriting this cosmetically by setting $j = n - (p-1)m$ and $k = n - pm$, the coefficient of $c_n$ in the expression for $P^m(c_{n-(p-1)m})$ is
$$ \frac{n}{n - (p-1)m} {n - (p-1)m \choose m} = \frac{n}{m} { n - (p-1)m - 1 \choose m-1} . $$
Specialising to $m = 1$, the $c_n$-coefficient in $P^1(c_{n - p + 1})$ is simply $n$. (Sanity check: this is not too hard to check by hand, see Equation 12.3 in Groupes de Lie et Puissances Reduites de Steenrod by Borel and Serre.) Hence, for any $n > p$ that is not divisible by $p$, we can express $c_n \textrm{ mod } p$ in terms of $P^1(c_{n-p+1})$ and products of Chern classes in lower degrees.
More generally, for any $s \geq p$ and $r \geq 0$, the coefficient of $c_{p^r s}$ in the expression for $P^{p^r}(c_{p^r(s - p + 1)})$ is
$$s \, {p^r(s-p+1) - 1 \choose p^r - 1} . $$
The binomial factor is never divisible by $p$, so this coefficient is non-zero mod $p$ if and only if $s$ is coprime to $p$. Thus $c_{p^r s}$ can be expressed in terms of products and Steenrod powers of Chern classes of lower degree whenever $s \geq p$ is coprime to $p$.
The conclusion is that $H^*(BU, \mathbb{Z}/p)$ is generated over the Steenrod algebra by Chern classes in degree $p^r s$ for $r \geq 0$ and $s = 1, 2, \ldots p-1$, and we can also see that the classes in those degrees cannot be removed from the generating set.
Combining this with the definition of Pontrjagin classes, we see that the Pontragin classes mod $p$ are generated over the Steenrod algebra by Pontrjagin classes in degree $p^r s$ for $r \geq 0$ and $s = 1, \ldots, \frac{p-1}{2}$.
