Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Hint what is $4 mod 3$. – Amzoti Dec 16 '12 at 18:50
up vote 2 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.