# How to check if a congruence equation is right or false

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)

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.

Generally it's a good plan to make the absolute value of the base small first, and worry about the exponent next.

Probably the question requiring most thought is #1).

$99 \equiv -2 \bmod 101$, and $101$ is prime so $(-2)^{100} \equiv 1$ from Fermat's little theorem.

IF the assertion were true, then $(-2)^{99}\equiv -1 \bmod 101$, but then we would have $(-2)^{100}\equiv -2\cdot -1 \equiv 2 \bmod 101$ which we know is not so. So; false.

Being comfortable with the negative version of the congruence can be very useful in these questions.

You have to reduce the number under the exponent and use lil' Fermat when the modulus is prime:

1. As $101$ is prime, $$99^{99}\mod 101\equiv (-2)^{99\bmod 100}=(-2)^{-1}\mod 101.$$ Now $2\cdot 51\equiv 1\mod 101$, so $2^{-1}\equiv 51$ and $(-2)^{-1}\equiv -51\equiv 50\mod 101$
2. As $97$ is prime $$99^{99}\equiv 99^{99\bmod 96}=99^3\equiv (99\bmod97)^3=2^3\mod 97.$$

For the nonprime moduli, we may have to compute the value of the totient function at these, but it won't be necessary in the present cases:

1. $99^{99}\mod 98\equiv 1^{99}=1\mod 98$.
2. $99^{99}\equiv (-1)^{99}=-1\mod 100$.