How to check if a congruence equation is right or false

Question

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)

Answer 1

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$.

Answer 2

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.

Answer 3

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.