2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 28, 2011 at 16:38
  • $\begingroup$ Any specific choice of $a$ and $b$ works for all but finitely many primes $p$.... $\endgroup$
    – Greg Martin
    Commented Jul 28, 2011 at 19:35
  • 3
    $\begingroup$ 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$). $\endgroup$
    – Greg Martin
    Commented Jul 28, 2011 at 19:43
  • 1
    $\begingroup$ Actually, p=23 has a counterexample, if I read the question right. Gerhard "Ask Me About Small Cases" Paseman, 2011.07.28 $\endgroup$
    – Gerhard Paseman
    Commented Jul 28, 2011 at 20:59
  • 4
    $\begingroup$ n=3. In rewriting the problem n=2 should also be excluded. Gerhard "Ask Me About System Design" Paseman, 2011.07.28 $\endgroup$
    – Gerhard Paseman
    Commented Jul 28, 2011 at 22:50

1 Answer 1

Reset to default
1
$\begingroup$

Here is a partial attempt at an answer. If we're lucky, it will attract someone's attention (Gjergji? Noam?) and they will resolve the question.

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

I will post more as ideas occur to me on this probllem.

Gerhard "Ask Me About System Design" Paseman, 2011.07.31

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Aug 14, 2011 at 23:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .