Can you prove a number is prime with evidence? Hypothetically, I am 100% confident that a large multi-million digit number is prime because I expended the resources to run an extensive primality test. Let's say the number Truly is a prime. Is there any proof I could provide that would save others from having to run more extensive tests?
We can do the opposite, I can hand over a big number and say it's not prime by providing evidence: a factor. Depending on the size of numbers it may still take a non-trivial amount of time to prove it, but it would take comparably much less time than starting a primality test from scratch.
 A: Yes. There are various theorems about prime numbers stating that if $n$ meets condition $X$ then $n$ is definitely a prime number. Some of those theorems depend on $n - 1$, which is a very easy calculation. We can use, for example, the converse of Fermat's "little" theorem to create a Pratt certificate.
Let's say, for the sake of example, that 139 is prime but we're not allowed to use trial division to prove that it is prime (even though a computer can do it in a nanosecond, if even that long).
Clearly 138 is composite, as it's divisible by 2, 3 and 23. We see that $141^{138} \equiv 1 \pmod{139}$. But $$141^{\frac{138}{2}} = 141^{69} \equiv 138 \pmod{139},$$ $$141^{\frac{138}{3}} = 141^{46} \equiv 96 \pmod{139}$$ and $$141^{\frac{138}{23}} = 141^{6} \equiv 64 \pmod{139}.$$
The important thing is that none of those congruences are equal to 1.
So 141 is a "witness" for a Pratt certificate for 139. Of course making a Pratt certificate for 139 is overkill. But for a prime with 139 digits, it's preferable to trial division.
According to Wolfram Mathworld, Wolfram Mathematica uses Pratt certificates for numbers below $10^{10}$ and the more sophisticated Atkin-Goldwasser-Kilian-Morain certificates for larger numbers.
