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.

  • 0
    Hint what is $4 mod 3$.2012-12-16

3 Answers 3

2

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$

1

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.

  • 0
    Ok lets assume it doesn't cover all the residues.2012-12-16
1

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$