I have a homework assignment to find the two smallest probable primes with $12$ digits, where a probable prime is defined as a number such that $a^{p-1} \equiv 1\ (\textrm{mod}\ p)$, where $a = 2, 3, 5, 7$.
I'm obviously not asking for this to be done for me, but I'm having trouble figuring out a way to do anything other than to brute-force it by checking each of the four congruences for each (odd) $12$ digit number $n$ until I find two of them.
Can someone offer me some hint, relevant theorem, or something that I might be able to use to figure out how to do find these numbers in a more efficient manner? Thanks for any help.