Most elegant way to prove a prime is a prime? Taking say 103, the best way I can think of is to square root it (giving 10.14889), then say that all factors must be below that root, then show that 103 is not divisible by 2,3,5,7 (prime factors below the square root), and is therefore prime?
Is there a better way to prove it is a prime, or is this the best way?
 A: For small odd numbers, say below $10^6$, there is just no better way than trial division: try dividing $n$ by each prime less than $\sqrt n$ and see what happens. Heck, you can even try dividing by all odd numbers, including composite numbers like $9$ and $15$, with hardly any performance penalty (assuming you're using a computer).
When you go above $10^{10}$ (these are not hard limits, more like fuzzy gray lines) things start getting hairy and you need something more elegant in order to get results in your lifetime.
For example, is $2^{44501} - 1$ prime? This is a number with more than ten thousand digits in base $10$, and $44500$ bits in binary. Trial division just won't cut it.
Mathematicians have developed all kinds of tests for primes of special forms. I could be wrong, but $103$ doesn't seem all that special. Now consider a number like $127$. It's special because it's $2^7 - 1$. Because $11 < \sqrt{127}$, it's enough to test the primes $3, 5, 7, 11$.
The Lucas-Lehmer test applied to $127$ seems kind of overkill, except for pedagogic purposes. Set $LL_0 = 4$, and then $LL_n = (LL_{n - 1})^2 - 2$. If $2^p - 1$ is prime, then $LL_{p - 2} \equiv 0 \pmod{2^p - 1}$. The proof is too long to repeat here but can be found on the Web easily enough. So modulo $127$, we have: $4, 14, 194, 42,  111, 0$, bingo!
When you start to look at numbers like $2^{31} - 1$, then you can really appreciate things like the Lucas-Lehmer test. But to deal with large odd numbers that don't seem to be of any special form, there are algorithms like Pollard $p - 1$ and Pollard $\rho$, which have their best case and worst case scenarios (e.g., hardly any better than trial division).
