If one can know for certain that a given integer is composite, why is it apparently so difficult to find its factors? Why doesn’t knowing that something exists give one a recipe for determining what that something is?

The reason this is possible is that there are *further properties* of prime numbers (theorems about prime numbers), so if your number doesn't fit such a property then it can't be prime without having to know how the number isn't prime in an explicit way.

**Example**. If $p$ is prime then $a^{p-1} \equiv 1 \bmod p$ for *all* $a$ from 1 to $p-1$, so if $n \geq 2$ and we can get $a^{n-1} \not\equiv 1 \bmod n$ for *even one* $a$ from $1$ to $n-1$ then $n$ isn't prime, and this isn't because we found a nontrivial factorization of $n$: we showed $n$ doesn't satisfy a property that all prime numbers satisy, which goes *beyond* the mere definition of prime numbers. For example, taking $n = 17399$, $2^{n-1} = 2^{17398} \equiv 16518 \not\equiv 1 \bmod n$, so $n$ is not prime and the reason we know this is not due to how $n$ factors. So we don't learn from this a way to factor $n$. Of course $n$ is small enough that a computer reveals $n = 127 \cdot 137$ immediately, but for very large numbers there can be a huge gap in time between knowing $n$ is not prime and knowing a nontrivial factor. Consider $n = 2^{2^{14}}+1$, the $14$th Fermat number. It has 4933 digits and was proved to be
composite in 1961 by Hurwitz and Selfridge, but a nontrivial factor of this number was first found nearly 50 years later, in 2010.

This kind of phenomenon (properties that go beyond the initial definition of a concept) is not at all limited to primes vs. composites.

**Example**. Consider the property of having unique factorization. In $\mathbf Z$ and the polynomials $\mathbf R[x]$ there is unique factorization. Rings with unique factorization all satisfy a number of properties that are not just about the definition, so a ring that doesn't satisfy such a property fails to have unique factorization and it isn't because we must know an explicit counterexample to the unique factorization property directly. For instance, all rings with unique factorization are integrally closed, and $\mathbf Z[\sqrt{5}]$ is not integrally closed (the number $(1+\sqrt{5})/2$ in the fraction field is a root of the monic polynomial $x^2 - x - 1$ with coefficients in $\mathbf Z[\sqrt{5}]$ without being in $\mathbf Z[\sqrt{5}]$), so $\mathbf Z[\sqrt{5}]$ doesn't have unique factorization and the reason we know this is not from finding an explicit counterexample in $\mathbf Z[\sqrt{5}]$ to unique factorization.

More generally, for every $d \in \mathbf Z$ that is not a perfect square and satisies $d \equiv 1 \bmod 4$, $\mathbf Z[\sqrt{d}]$ is not integrally closed because $(1+\sqrt{d})/2$ is a root of $x^2 - x - (d-1)/4$, and thus it does not have unique factorization, and I did not need to contradict the unique factorization property explicitly to show these rings don't have unique factorization: I showed they all fail to satisy a property (being integrally closed) that is common to all rings with unique factorization.

9more comments