Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Hint what is $4 mod 3$. –  Amzoti Dec 16 '12 at 18:50
add comment

3 Answers

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|improve this answer
add comment

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|improve this answer
    
Ok lets assume it doesn't cover all the residues. –  Ethan Dec 16 '12 at 18:56
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.