[NobleSir]

My favorite proofs of these basic number theory facts are in Apostols, Intro to Analytic Number Theory. At best the FTA using the proof there is only slightly less than obvious (of course obviousness probably varies widely based on mathematical background / maturity).

[Chinjut]

Sure, to a mathematician, these things become old hat, but note that Apostols spends several pages developing properties of the GCD that aren't generally considered "obvious"; in particular, he argues for Theorem 1.2 (that any two integers a and b have a common divisor of the form ax + by, which is in turn therefore divisible by all their other common divisors) by tracing out the steps to recursively compute this combination-as-GCD (i.e., the Euclidean algorithm), recast as an inductive proof. I don't think the layperson would find this obvious at all (in the way they might have claimed FTA to be obvious), or even be aware of this fact, though it plays a key role in building up to the eventual proof of the FTA.