Optimal Algorithm for checking if a number is a multiple of three
If an algorithm that takes less than $O(n)$ time, this means that the algorithm won't be able to look at all the digits of the number. Thus you can prove a lower bound of $O(n)$ by showing that you have to look at all (or almost all) digits of the number in order to decide divisibility.

To show the latter property, assume you had an algorithm that decides divisibility by 3 by looking at $n-2$ or fewer of the digits. This gives you 2 digits that you can set freely, since the algorithm has to give the same answer for any choice of these digits (it doesn't look at them) and it has to be always correct. However you can show that no matter where these digits are and what the value of the remaining digits is, you always have a choice for the digits that gives a number divisible by 3 and another choice that doesn't. Thus, the assumed algorithm can not exist. (I'll leave it to you to show the existance of such choices.)