We ought never to allow ourselves to be persuaded of the truth of anything unless on the evidence of our own reason – René Descartes

Proof: a natural number n is a prime if b^(n−1) = 1 (mod n) for every integer b between 1 and n-1

Prove or disprove: A natural number n ≥ 2 is a prime if ${b}^{n-1}\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$
for every integer b between 1 and n − 1.

Suppose not.
Suppose that there is a natural number $n\ge 2$, which is a not prime but
${b}^{n-1}\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$ for all $1\le b\le n-1$.

Because n is not a prime, there must be integers r and s both greater than 1 such that $n=rs$.
Because $1<r<n$, it follows that ${r}^{n-1}\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$ by our assumption.
By the definition of congruence modulo n, there exists k such that ${r}^{n-1}-1=kn$.
Thus, ${r}^{n-1}-kn=1$ and $1={r}^{n-1}-krs=r({r}^{n-2}-ks)$.
But this is impossible since $r>1$.
Thus, our supposition is false, and any natural number $n\ge 2$
such that ${b}^{n-1}\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$ for all $1\le b\le n-1$ is a prime.
Q.E.D.

In my failed attempts to prove this statement, I accidentally proved the following two theorems.
Since the results are pretty nice, I'll include it here.

If k, r, and s are integers, n is a prime, and k is not divisible by n and
$kr\equiv ks\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$, then $r\equiv s\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$.

Proof: Let k, r, s, and n be integers such that $gcd(n,k)=1$ and $kr\equiv ks\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$.
By the definition of congruence modulo n, $n\mid (kr-ks)$ or that $n\mid k(r-s)$.
By Euclid's lemma (for all integers a, b, and c, if $gcd(a,c)=1$ and $a|bc$, then $a|b$),
$n\mid (r-s)$ since $gcd(n,k)=1$.
Thus by the definition of congruence modulo n, $r\equiv s\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$.
Q.E.D.

If a is an integer and b is a prime, then ${a}^{b-1}\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$.

Proof: Let a be any integer and b be any prime.
Then a ≠ 0 because otherwise $gcd(a,b)=b$.

Consider a set $P=a,2a,3a,\dots (b-1)a$.
Suppose $ka\equiv ma\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$ for some integers k and m such that 1 ≤ k < m ≤ b.
Since $gcd(a,b)=1$, $latexk\equiv m\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$ by the cancellation law.
By the definition of congruence modulo b, $b|(k-m)$.
But this is impossible since $0<k-m<b$.
Thus, every element in P belongs to a distinct equivalence class defined by congruence modulo b.

Now let us define a function F from P to a $Q=1,2,3,\dots (b-1)$ defined
as $F(p)=p,mod,b$.
Then F is one-to-one because every element in P belongs to a distinct equivalence class
defined by congruence modulo b, and Q is simply a set of the class representatives.
Furthermore, F is onto because because F is one-to-one and P and Q have the same cardinality.

Thus, ${a}^{b-1}(b-1)!\equiv {a}^{b-1}{\displaystyle \prod _{i=1}^{b-1}i\equiv {\displaystyle \prod _{i=1}^{b-1}i\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)}}$
by the commutative law of modular arithmetic.
Because b is a prime, $gcd({\displaystyle \prod _{i=1}^{b-1}i,b)=1}$.
Applying the cancellation law yields: ${a}^{b-1}\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$ as desired.
Q.E.D.