It comes done to proving that has only and as its solutions. By far the best way to prove this is over the unique factorization domain . Because you can factor the left hand side as .
Of course Fermat did not in any way prove this using the idea above. Unique factorization was only developed about 100 years ago by Kummer/Kronecker. I have no idea how Fermat, or Euler who later solved it also, did it by using elementary results.