2
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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