Question

I don't think that proofs are about replacing 99% certainty with 99.99% (or 100%, if the proof is simple enough). In one of his problems he studied early on, Fermat stated that it was important to find out whether a prime divides only numbers $a^n-1$, or also numbers of the form $a^n+1$. For $a = 2$ and $a = 3$ he saw that the answer seemed to depend on the residue class of $p$ modulo $4a$. He did not really come back to investigate this problem more closely; Euler did, but couldn't find the proof. Gauss's proofs did not remove the remaining 1 % uncertainty, it brought in structure and allowed to ask the next question. Just looking at patterns of prime divisors of $a^n \pm 1$ wouldn't have led to Artin reciprocity.