Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo $p$ must have high complexity in every other characteristic $q$.
More precisely, we show the following results about Boolean functions $f:\{0,1\}^n \rightarrow \{0,1\}$ which depend on all $n$ variables, and distinct primes $p,q$:

\begin{itemize}
\item If $f$ has degree $o(\log n)$ modulo $p$, then it must have degree $\Omega(n^{1-o(1)})$ modulo $q$. Thus a Boolean function has degree $o(\log n)$ in only one characteristic. This result is essentially tight as there exist functions that have degree $\log n$ in every characteristic.

\item If $f$ has degree $d = o(\log n)$ modulo $p$, it cannot be computed correctly on more than $ 1- p^{-O(d)}$ fraction of the hypercube by polynomials of degree $n^{\frac{1}{2} - \eps}$ modulo $q$.
\end{itemize}

As a corollary of the above results it follows that if $f$ has degree $o(\log n)$ modulo $p$, then it requires super-polynomial size $\AC_0[q]$ circuits. This gives a lower bound for a broad and natural class of functions.