Smallest Prime

For odd natural number $n$ , we have $a^n + b^n = (a+b)(a^{n-1} - a^{n-2}b + a^{n-3}b^2 + ... + a^2b^{n-3} - ab^{n-2} + b^{n-1})$ , therefore, $a^n + b^n$ is divisible by $a+b$ for odd $n$ . Therefore, $2^{111} + 3^{111}$ is divisible by $2+3 = \boxed{5}$ , which is a prime.

The last digits of $2^n$ repeat in the cycle $2,4,8,6$

The last digits of $3^n$ repeat in the cycle $3,9,7,1$

So the last digits of $2^n+3^n$ repeat in the cycle $5,3,5,7$

Notice that the last digits of $2^n+3^n$ is $5$ whenever $n$ is odd.

Alternatively, $a^n+b^n$ is divisible by $a+b$ for every odd $n$ .

So $2^{111}+3^{111}$ is not divisible by $2$ or $3$ .

So the smallest prime factor of $2^{111}+3^{111}$ is $5$ .