Not sure if the following argument is circular in nature or breaks down in some other way.
We've defined the counting numbers $n \ge 1$ with the two familiar binary operations of addition and multiplication.
From this point all numbers will be greater than $1$.
We don't rush into things so we have no symbol for the number succeeding $1$, and also haven't defined the notion of divisibility or formulated Euclidean division.
Definition: A number greater than $1$ is said to be a prime number if it is not in the range of the multiplication operator, $(m,n) \mapsto m \times n$, when it is restricted to $\Bbb N^{\gt 1} \times \Bbb N^{\gt 1}$. All other numbers greater than $1$ are said to be composite numbers.
Proposition 1: Every composite number can be expressed as the product of primes.
Proof
Assume $n$ is a composite number that can't be expressed as a product of primes. Since it is a composite we can write $c = ab$. Now if both $a$ and $b$ can be written as a product of primes, then $c$ has such a representation. So, wlog, assume that $a$ can't be written as a product of primes. But then we have found a number $a \lt c$ that has no such representation.
By the method of infinite descent, we've reached an absurdity. $\quad \blacksquare$
Corollary 2: There exist both composiste and prime numbers.
Proof
The multiplication operator has a nonempty domain, so there exist at least one composite number $a$. Since $a$ can be written as a product of primes, there must also exist prime numbers. $\quad \blacksquare$
You need the well-ordering principle, which is equivalent to the induction principle: every non-empty set of natural numbers has a least element.