Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
3  
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
1  
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
4  
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
show 1 more comment

1 Answer

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.