  Let $\mathcal{K}(a)$ denote the Kloosterman sum on the finite field of order
$2^n$. We give a simple characterization of $\mathcal{K}(a)$ modulo 16, in
terms of the trace of $a$ and one other function. We also give a
characterization of $\mathcal{K}(a)$ modulo 64 in terms of a different
function, which we call the lifted trace. Our proofs use Fourier analysis,
Stickelberger's theorem and the Gross-Koblitz formula.
