Modular Arithmetic Remainder Congruency such as $98765 ^ {54321} \bmod 7$ I'm trying to figure out how to find the remainder of large numbers not in mod 10 by doing different examples.
Something that I'm working on is $98765 ^ {54321}$ (mod 7). 
Can anyone help me find a general way to do these types of problems?
 A: There are several methods you can apply to try to solve problems of the form:
$x \equiv n^a$ (mod $m$)


*

*First, you can try to find the smallest positive $y \equiv n$ (mod $m$), and replace $n$ with $y$ in the original congruence. Note that it is sometimes helpful to replace it with $y-m$ instead of $y$ if $|y-m|<y$.



For example, if $x \equiv 11^a$ (mod 4), then you can replace the 11 with -1 or 3, as $11 \equiv 3 \equiv -1$ (mod 4).
In this case, it would probably be more helpful to use -1, as its absolute value is less than 3, and so it is easier to take powers of -1 than 3.
$x \equiv 11^a \equiv (3(4)-1)^a \equiv (3(0)-1)^a \equiv -1^a$ (mod 4)

So using this method, you now have:
$x \equiv y^a$ (mod $m$), where $y$ is a relatively small number.
If $a$ is large, and the number you are taking powers of is not 1 or -1, then there are 2 methods which are usually used to cancel the congruence down:


*If $m$ is a prime, $p$, then you can use Fermat's little theorem to simplify the congruence:
$a^p \equiv a$ (mod $p$)
or more usefully:
$a^{p-1} \equiv 1$ (mod $p$) if $a$ is not divisible by $p$.
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

For example, if $x \equiv 3^{1000}$ (mod 7), then using Fermat's little theorem, you know that: $3^6 \equiv 1$ (mod 7).
Then you can rewrite the congruence as: $x \equiv 3^{6(166) + 4}\equiv {(3^{6})}^{166} \times 3^4 \equiv {1}^{166} \times 3^4 \equiv 3^4$ (mod 7).
This can often allow you to simplify the congruence down to something you can calculate.



*On the other hand, if Fermat's little theorem does not help (or does not help you simplify it down to small and manageable numbers), then try taking powers of $y$ (mod $m$), and seeing if these result in small numbers.



For example, if $x \equiv 5^{101}$ (mod 12), then you cannot use Fermat's little theorem as 6 is not prime.
However, notice that $5^2 \equiv 1$ (mod 12).
Hence: $x \equiv 5^{2(50) + 1} \equiv (5^2)^{50} \times 5^1 \equiv 1^{50} \times 5 \equiv 5$ (mod 12).

I hope this helps.
A: First reduce the base mod 7.  Since $98765\equiv 2\mod 7$, we want to find
$$2^{54321}\mod 7$$
Since 2 and 54321 are relatively prime, using Euler's theorem, we can reduce 54321 mod $\phi(7)$.  Since $54321 \equiv 3 \mod 6$, we want to find $$2^3 \mod 7$$
The answer in this case is 1.
