# Another Question About Powers mod p

Given any positive integer $n$ and prime number $p$, I would like to show that one can write $n$ as a sum of positive integers $a+b$ so that $a^ab^b$ is not congruent to $n^n$ mod $p$. One can easily show this is true for $n \ge p$, so one can restrict attention to the case where $n$ is less than $p$.

Experimentally, Mathematica tells me that for all $n$ less than 10,000 one can get away with choosing $a$ to be less than $4$ (ie there is no number in that range with $n^n \equiv (n-1)^{(n-1)} \equiv 4(n-2)^{(n-2)} \equiv 27(n-3)^{(n-3)}$ mod $p$), and in fact the least residues of the products we are interested in tend to have very little overlap, so this is "certainly" true (as much as we can ever say that in mathematics without having a proof), but I don't see a way to prove it. Any thoughts?

-
Let n be even and a=b. This works for all but finitely many primes p. Perhaps a simple variation can handle the remaining p, and you might do something similar for composite n. Gerhard "Ask Me About System Design" Paseman, 2011.07.28 –  Gerhard Paseman Jul 28 '11 at 16:38
Any specific choice of $a$ and $b$ works for all but finitely many primes $p$.... –  Greg Martin Jul 28 '11 at 19:35
I'm not sure this is helpful, but when $a+b=n$ and $a$ and $n$ are relatively prime, then $n^n - a^a b^b$ is the discriminant of the trinomial $x^n - x^a + 1$ (equivalently, of $x^n - x^b + 1$). –  Greg Martin Jul 28 '11 at 19:43
Actually, p=23 has a counterexample, if I read the question right. Gerhard "Ask Me About Small Cases" Paseman, 2011.07.28 –  Gerhard Paseman Jul 28 '11 at 20:59
n=3. In rewriting the problem n=2 should also be excluded. Gerhard "Ask Me About System Design" Paseman, 2011.07.28 –  Gerhard Paseman Jul 28 '11 at 22:50

If there are enough sums of the form $a^ab^b$ the result is most likely true for a given $n$ and any prime $p$. Note that are not enough sums when $4 > n$. An equivalent formulation, using $c=a+1$ and $b=d+1$, is to find nonnegative $a,b$ with $a+b=n$ such that $a^ab^b \neq c^cd^d$ mod $p$ .
Suppose $k$ is coprime to $p-1$ (Edit: and $p > k$). If $a^ab^b \neq n^n$ mod p, then $(ak)^a(bk)^b \neq (nk)^n$ mod $p$ and the inequality holds when everything is raised to the power $k$. If one is lucky to find a satisfying decomposition of $nk$ into $ak$ and $bk$, then one can reverse the process, again assuming $k$ is coprime to $p-1$ (because then $k$th roots mod $p$ are unique).
More generally, for n=hk composite, one can "remove" some factors of n from consideration, reducing the problem to $(h^h)^k = ((a^a)(b^b))^k$ mod $p$, or not equals mod $p$. For $h=2$, this gives that $p$ must be a factor of $4^k - 1$. Gerhard "Ask Me About System Design" Paseman, 2011.08.14 –  Gerhard Paseman Aug 14 '11 at 23:45