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)}$.

  • 0
    Wow, great explanation in a very little time. Then, if $f$ is _not_ a polynomial with integer coefficients the result is, in general, false?2011-12-11
  • 0
    @Bruno: It will depend on the function $f$, yes; there may be other classes of functions for which the implication holds, though probably not via Fermat's Little Theorem.2011-12-11
  • 0
    You're probably right, I've proved the statement for a few non-polynomial functions but this could only be done in a case-by-case basis. Even if it was true for all non-polynomial functions, which is not, it's would be most likely impossible to prove it for every possible integer function.2011-12-11
  • 0
    @Bruno: Well, it is certainly impossible to prove it for every possible integer function, because I already gave you an example of an integer function for which the result is *false*... If you could prove it for every integer function, we would be in serious trouble (it would mean mathematics is inconsistent!)2011-12-11
  • 1
    Haha, yes, that would be an awkward situation2011-12-11