Proving primality of $p$ without making any calculation involving $p$ directly

80 Views Asked by At

Wilson's Theorem states that a positive integer $p > 1$ is prime if and only if $(p-1)! \equiv -1 \pmod p$, showing a relationship between factorials and prime numbers. Finding it curious, today I started trying to understand why it happens by looking for other relationships between them; I ended up dividing the factorial by its analogous sum function, that generates the triangular numbers (the $nth$ triangular number is the sum of all positive integers up to $n$, inclusive), and found out that they are related indeed.

Let $T_n$ denote the $nth$ triangular number and $q=p-1$. I noticed that the following congruences $$A:\ q!\equiv T_q-1\pmod{T_p},$$ $$B:\ q!\equiv q \pmod{T_q},$$ and $$C: (q-1)!\equiv T_{(q-1)}\pmod{T_q}$$ hold, apparently, if and only if $p>2$ and $p$ is prime.

For all other cases, i.e. when $p$ isn't prime, $T_p\mid q!$, $T_q\mid q!$, and $T_q\mid (q-1)!$. I found the last congruence (congruence $C$) especially interesting, because it means that the primality of a positive integer $p>2$ can be proven without making any calculation involving $p$ itself. If true, it means: let $q$ be an even integer such that $q>2$, then $q+1$ is prime if and only if $T_q\nmid (q-1)!$.

I can't prove or disprove these congruences, however. I couldn't find anything related to them on internet either. Can anyone help? Also, is there any known primality test that doesn't involve directly the integer being tested?

Thanks.