Kolmogorov Complexity applications in Number Theory
Every integer has an associated Kolmogorov complexity; the shortest program that prints that integer.

There are $\approx {x \over ln(x)}$ primes up to $x$ so primes have lower Kolmogrov complexity than composites on average; $\approx ln({x \over ln(x)})$    vs  $\approx ln(x)$.

As a side effect you have to have some large gaps between primes; otherwise you could encode every number as the previous prime plus some small number of bits.