Proth's theorem

Theorem. Let $N=k\cdot2^n+1$ with $k<2^n$ odd. $N$ is prime iff there exists $a$ with $a^{(N-1)/2}\equiv-1\pmod N$.

Apply to $N=49$. $49=3\cdot2^4+1$, so $k=3$, $n=4$, $(N-1)/2=24$. Need $a^{24}\equiv-1\pmod{49}$. Try $a=3$: $3^{24}=(3^6)^4=729^4\equiv729\equiv-8\pmod{49}$... compute more carefully. Actually $49=7^2$, not prime, so no such $a$ exists.

Correction. $49=7^2$ is composite; Proth's theorem confirms no such $a$ exists.

Conclusion. The theorem is used to certify primality of Proth numbers efficiently.