I remember seeing this problem somewhere... I know the answer, but I honestly didn't look at the solution to it...

Answer

The value of $36^k - 5^m$ will always be congruent to $1$ modulo $5$. From above we know $11$ is achievable, the only possible smaller values would be $1$ and $6$. If we take the expression modulo $6$ we get $36^k - 5^m \equiv -(-1)^m \mod 6$ so the expression will never be divisible by $6$, meaning $6$ is not possible. The only other possibility is $1$. Assume for contradiction $36^k - 5^m = 1$. This rearranges to $(6^k-1)(6^k+1) = 5^m$. Since $m \geq 1$ then $6^k-1$ and $6^k+1$ must both be powers of $5$. This implies existence of two powers of $5$ that are spaced $2$ apart. But this is never possible (minimum is $5-1 = 4$, easy to show with induction that the difference only increases). So $1$ is not possible and the minimum value must be $11$.

$36^k - 5^m \equiv 3 \pmod4$ i.e. $36^k - 5^m \in \{3,7,11, ...\}$ Similarly $36^k - 5^m \equiv 1 \pmod5$ i.e. $36^k - 5^m \in \{1,6,11, ...\}$ The least common element in the above two set is $11$ which is attainable at $k=1, m=2$ $\therefore min\{36^k - 5^m\}=11$ ,such that $36^k - 5^m >0$