This is an update on my 2019 post on the subject. This new proof is even simpler and (hopefully) better explained.
Here's a simple, fairly non-algebraic and not particularly rigorous proof of the Fundamental Theorem of Arithmetic. The theorem states that any natural number >1 can be uniquely expressed (apart from re-ordering) as a product of primes. For example, 140 = 2 x 2 x 5 x 7 and there is no other set of primes that multiply together to make 140.
It is obvious by construction that any natural number can be expressed as some product of primes. Now, if the Fundamental Theorem of Arithmetic is false, then, for some such natural number, there is another set of primes with the same product. We can divide out any prime that appears in both sets, so that we end up with two sets of primes with equal products and no primes in common.Now take the largest prime P (looking over both sets). We need to show that P does not divide into the product of primes in the other set. We do this by induction, building up the product in the other set. We note that P does not divide into the first factor in the other set because that is prime (and because it is smaller than P). Then if P does not divide into the product so far, we show that it won't divide into that product multiplied by the next factor.
Let R be the current product, and N the next factor. So we know that P does not divide into R, and we want to show that P does not divide into NR.
Instead of worrying about N itself, we look for the smallest number k between 2 and P-1 inclusive for which P divides into kR. If we can prove there is no such k, we have also proved that P does not divide into NR, since we know that N is between 2 and P-1.
So suppose such a k does exist. Now look at the largest multiple of k that is less than P. Call this sk. Then P divides skR. But P also divides PR (obviously), so P divides (P-sk)R. But P-sk <= k (otherwise sk wasn't the largest multiple). And P-sk is not equal to k (otherwise P = k(s+1) and P would not be prime) so p-sk < k. So k wasn't the smallest after all. So there is no such k, including in particular the next element N in our product. So P does not divide into NR. Continuing this argument until we have reached the last element in the product, we have shown that P does not divide into the other product of primes, so the theorem is true.
