# Modular arithmetic help

Given fixed $a,p$ how can I show that $a^n$ mod p is never equal to a given number, for any integer n?

For example how can I show that $4^n$ mod 3 is never equal to 2.

• Hint what is $4 mod 3$. – Amzoti Dec 16 '12 at 18:50

## 3 Answers

Show that it cycles:

$$4^0 \equiv 1 \mod 3\\ 4^1\equiv 1 \mod 3\\ 4^n\equiv 1^n\equiv 1 \mod 3$$

It really depends on what $a, p$ are. For example, if $a$ is a primitive root modulo $p$ and $p$ is a prime, then the question doesn't make any sense if the given residue is nonzero, as then $a^n$ will cover all nonzero residues.

For your specific case, though, Michael Boratko's answer suffices.

• Ok lets assume it doesn't cover all the residues. – Ethan Dec 16 '12 at 18:56

It is always true that $\,a^p=a\pmod p\,$ , if $\,p\,$ is a given prime number and $\,a\in \Bbb Z\,$.

In the example you give though,

$$4=1\pmod 3\Longrightarrow \,\forall\,n\in\Bbb N\,\,,\,4^n=1^n=1\pmod 3\,\,\text{and}\,\,\, 1\neq 2\pmod 3$$