1
$\begingroup$

I'm aware this is an extremely amateur question but I really don't know where else to ask it. Can anybody find a counterexample for the following conjecture?

Given $f$ such that $f:A\subseteq\mathbb Z^n \to\ B\subseteq\mathbb Z$, if $f(x)$ is prime, then

$f(x^{f(x)}) \bmod f(x) = 0$

1 Answers 1

4

The result is true if $f$ is a polynomial with integer coefficients.

By Fermat's Little Theorem, if $p$ is a prime and $a$ is an integer, then $a^p\equiv a\pmod{p}$.

By standard arguments, if $g(x)$ is any polynomial with integer coefficients, and $a\equiv b\pmod{n}$, then $g(a)\equiv g(b)\pmod{n}$.

Assume that $f(b) = p$ is a prime. Then $a^{f(b)} \equiv a \pmod{f(b)}$ for all $a$. If $g$ is any polynomial with integer coefficients, it follows that $g(a^{f(b)}) \equiv g(a)\pmod{f(b)}$ for all $a$.

In particular, taking $g(x)=f(x)$, we get that $f(b^{f(b)}) \equiv f(b) \equiv 0 \pmod{f(b)}$ if $f(b)$ is a prime.

For a counterexample with a function that is not a polynomial, define $f\colon \mathbb{Z}\to\mathbb{Z}$ by $f(x) = 3$ if $x$ is a perfect square, and $f(x)=2$ if $x$ is not a perfect square. Then $f(a)$ is always a prime; if $f(a)=2$, then $f(a^{f(a)}) = 3$ (because $a^{f(a)} = a^2$ is always a perfect square), and so is not congruent to $0$ modulo $f(a)=2$. For example, $f(3)=2$, but $f(3^{f(3)}) = f(9) = 3\equiv 1\pmod{2}$, so $f(3^{f(3)})\not\equiv 0 \pmod{f(3)}$.

  • 1
    Haha, yes, that would be an awkward situation2011-12-11