How to find $n$ if $a^n \equiv r \pmod m$

Question

In particular I'm looking at the problem:

\begin{align*} 3^{n_1} &\equiv 1 \pmod 4 \\ 5^{n_2} &\equiv 1 \pmod 4 \\ 7^{n_3} &\equiv 1 \pmod 4 \\ \end{align*}

And I want to find $n_1, n_2, n_3$.

I've come up with one way, using binomial theorem:

\begin{align*} 3^{n_1} &= (4-1)^{n_1} = 4 \lambda_1 + (-1)^{n_1} \\ 5^{n_2} &= (4+1)^{n_2} = 4 \lambda_2 + 1 \\ 7^{n_3} &= (8-1)^{n_3} = 4 \lambda_3 + (-1)^{n_3} \\ \end{align*}

From where we see that $n_1$ and $n_3$ have to be even integers.

So, I have 2 questions:

1. Can this be done using modular arithmetic? And

2. Can this more general case be solved using modular arithmetic? $$a^n \equiv r \pmod m$$ for given $a, r, \text{ and } m$.

Answer 1

You need to look just a bit closer to the problem

\begin{align*} 3^{n_1} &\equiv 1 \pmod 4 \\ 5^{n_2} &\equiv 1 \pmod 4 \\ 7^{n_3} &\equiv 1 \pmod 4 \\ \end{align*}

Simplifies to

\begin{align*} (-1)^{n_1} &\equiv 1 \pmod 4 \\ 1^{n_2} &\equiv 1 \pmod 4 \\ (-1)^{n_3} &\equiv 1 \pmod 4 \\ \end{align*}

which simplifies to $n_1$ and $n_3$ are even and $n_2$ can be any integer.