As part of cryptography, if I wish to test whether a given number is probably prime I use the formula:
$$ a^{p-1} \equiv 1 \bmod p $$
where $p$ is (potentially) a prime number.
However, when it comes to testing a number such as 2341, i.e. $$2^{2341} \mod 2342$$ ... the numbers are two big for a calculator. I'm required as part of a course to generate a random 9 digit number and test for primality using the formula above.
Can I use congruence to reduce the numbers involved without invalidating the test?
Not sure how since shrinking the powers I'm shrinking the RHS of the equation and therefore testing another number completely for primality.
The short answer is yes.
This reduces to the problem of finding $a^b\pmod c$, for arbitrary nonnegative integers $a, b, c$, which can be done by Exponentiation by squaring.
If $b$ is even, we have $a^b=a^{2\times\frac{b}{2}}=\left(a^2\right)^\frac{b}{2}$.
If $b$ is odd, we have $a^b=a\times a^{b-1}=a\times\left(a^2\right)^\frac{b-1}{2}$
Since if $a\equiv a'\pmod c$ we have $a^b\equiv a'^b\pmod c$, we can reduce the base of the exponentiation $\pmod c$. As the power goes down by half, the algorithm will terminate in $O(\log b)$ steps.