If the lack of verbal communication was an issue, mutes wouldn't be able to function normally in our world. Some animals developed vocal communication, other visual (not necessarily using their eyes).
I don't know if animals know the concept of prime numbers, but analysing complex mathematical problem seems essential for their survival. I think of mathematics as an instinct rather then science. When I play with my cats with a toy hanged on a stick, I'm marvelled at their ability to predict the path and speed of the toy's movement and catch it - as if they were solving differential equations in real-time. Such "mathematical" skills are the condition of every hunter's survival.
I'm not sure what's your definition of communication, but there are lots of examples of effective exchange of information between humans and other animals: https://en.wikipedia.org/wiki/Human%E2% ... munication
If cooperation (the fishing with dolphins example) is communication, then probably Palaeolithic dog was first. Honeyguides in Africa are also worth mentioning.