How to find the general integer solution to an equation involving modulo with an unknown exponent?

Question

How do you solve a problem such as $$3^n\mod 10 = 9$$ for every integer solution for n? There is obviously a trivial solution for n=2 and I know from experimentation that the general solution would be $$n=2+4k$$ where k is an integer but how do you derive this from the equation?

Answer 1

Here's a way to look at it:

First note that $3^4\mod(10)=1$ and thus conclude from the properties of modulo under powers

$$3^{4k}\equiv1\mod10\Rightarrow3^{4k+2}\equiv9\mod10$$

It is easy to show by checking that numbers of the form $3^n$ are only $3,9,7,1\mod 10$ that there are no other solutions.

Answer 2

In general, if $a$ and $b$ are coprime there is some positive integer $m$ such that $a^m \equiv 1 \mod b$. The least such $m$ is called the order (or multiplicative order) of $a$ mod $b$. Then all $k$ such that $a^k \equiv 1 \mod b$ are multiples of $m$, and $a^x \equiv a^y \mod b$ if and only if $x-y$ is a multiple of $m$.

So in this case, once you know that $3^4 \equiv 1 \mod 10$ (and $3^1$, $3^2$, $3^3$ are not), the order of $3$ mod $10$ is $4$, and since $3^2 \equiv 9 \mod 10$ the solutions of $3^n \equiv 9 \mod 10$ are $n = 2 + 4 k$ for integers $k$.