Non-Euclidean geometry and the Pythagorean Theorem

Hey guys,

So, I'm doing a hand-drawn map- with latitude and longitude- of my main fantasy country for a novel. Here's the problem.

It is possible, in a Euclidean plane, to determine the distance between any two points by determining their up/down and left/right distances. That's called the Pythagorean theorem, and we all know it. But what about on a spherical planet? For example, one of my main cities is at 31.61 degrees south and 0 degrees east; another city is at 9.88 degrees east and 31.88 degrees south. The circumference of the planet is 3491.86 miles. If my calculations are correct, they should be about 700 miles apart. But I'm not sure, and my question is, is there a formula to determine the distance between two points on a planet of a certain radius if their longitude and latitude are given?