It was first stated by Euclid, in,
The Elements Book IX Proposition 14
Assume we know that we can factor any number into primes we wish to show that such a representation is unique.
Be the primes (not necessarily distinct) in non-decreasing order.
We know the left hand side is divisible by thus the right hand. Since they are prime, . That means . Similarly, the right hand side is divisble by thus, thus, . Thus, .
Dividing both sides by that we have,
If, then using the above arugument we can keep cancelling the left most primes on both sides eventually reaching,
Which is an impossibility.
Using the above argument we can then show,
for all .
I think this elegant proof using the basic property . Was developed by Gauss.