A specific problem I am struggling with is:
$99^{99} \equiv 8 (\textrm{mod}\ 97)$
But we are also having a test with only multiple choice questions on friday and a question can look like this:
Which of the following congruence equations are true/right/correct
#1) $99^{99} +1 \equiv 0 (\textrm{mod}\ 101)$
#2) $99^{99} \equiv 1 (\textrm{mod}\ 98)$
#3) $99^{99} \equiv 8 (\textrm{mod}\ 97)$
#4) $99^{99} +1 \equiv 0 (\textrm{mod}\ 100)$
What is a generell method to always be able to solve this no mater how you mix and tricks with the numbers? (I know about FERMAT'S LITTLE THEOREM, but I don't see how this can solve all of them completely)
Best Answer
You can't solve all of the above quite the same way. However there are other simple properties of congruences which you can use. $97$ is a prime, as is $101$ which makes things easy (easier for $97$, but note $99\equiv -2 \bmod 101$). For non-primes you can use the Fermat-Euler theorem if you like, and in some, but not all, cases (look this up if you don't know it, it is an extension of Fermat).
Here, though, note that $99\equiv 1\bmod 98$ and $99\equiv -1 \bmod 100$ and it is easy to raise $1$ or $-1$ to any power you choose. So if you are facing a similar question in a test, look to reduce the problem to a simpler one in this way.