To illustrate these ideas, let me give an information-theoretic proof that there are infinitely many prime numbers (Chaitin, 1979). Suppose on the contrary that there are only finitely many primes, in fact, K of them. Consider an algorithmically random natural number N. On the one hand, we know that H(N) is equal to log2 N + order of log log N, since the base-two numeral for N is an algorithmically random (log2 N)-bit string. On the other hand, N can be calculated from the exponents in its prime factorization, and vice versa. Thus H(N) is equal to the joint information of the K exponents in its prime factorization. By subadditivity, this joint information is bounded from above by the sum of the information contents of the K individual exponents. Each exponent is of order log N. The information content of each exponent is thus of order log log N. Hence H(N) is simultaneously equal to log2 N + O(log log N) and less than or equal to K O(log log N), which is impossible.