wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Factorial Equation
        
(Message started by: Sir Col on Mar 10^th, 2005, 8:33am)

Title: Factorial Equation
Post by Sir Col on Mar 10^th, 2005, 8:33am

Given that a, b, c are natural numbers, solve the following equation.

a! b! = a! + b! + c²

I posted this problem as one part of a collection of four in the Easy section and, rather embarrassingly, I either can't remember how I solved it or I made an error the first time round and never actually solved it at all.

Anyway, as it was posted in October 2003 and no one has solved it yet I am guessing that it is Hard. Although I've made reasonable progress in reducing it to a couple of cases, I am unable to fully solve it.

The original thread: Factorial Puzzle (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1066428889).

I uploaded my solutions to the other three from the collection to my website; these may influence your thinking on this problem for the better or worse.

a!b! = a! + b! (http://mathschallenge.net/index.php?section=problems&show=true&titleid=factorial_symmetry&full=true#solution)

a!b! = a! + b! + c! (http://mathschallenge.net/index.php?section=problems&show=true&titleid=factorial_equation&full=true#solution)

a!b! = a! + b! + 2^c (http://mathschallenge.net/index.php?section=problems&show=true&titleid=factorial_and_power_of_2&full=true#solution)

Upon reflection, the first was well placed in Easy, but the other two were perhaps better suited to Medium.

Title: Re: Factorial Equation
Post by TimMann on Mar 10^th, 2005, 9:09pm

Note that the hard part of this problem is proving that you've found all the solutions to the equation. So don't everyone jump in posting the easy-to-find small solution without proving it's unique.

Title: Re: Factorial Equation
Post by TimMann on Mar 28^th, 2005, 12:22am

I did some thinking about this puzzle, came up with one observation, and then got stuck. Looking at what Sir Col posted over in the original thread, my observation overlaps part of his partial result, so it doesn't really add much, but here it is.

Again, assume a >= b and divide through by b! to get a! = a!/b! + 1 + c²/b!. We know a!/b! is an integer, so c²/b! must be too. Consider the prime factorization of b!. Unless b! is itself a perfect square, at least one prime in its factorization must have an odd exponent. Let p be the least such prime. Then c²/b! must be divisible by p, because c² is divisible by b! but has only even exponents in its prime factorization. Also, p <= b <= a, so p divides a! as well.

Now, if p divides any n such that a >= n > b, then the equation has no solution, since the LHS is congruent to 0 mod p while the RHS is congruent to 1. Such an n certainly exists if b - a >= p. So b - a < p.

Part of Sir Col's result is the special case of the above where p = 2. I'm not sure my generalization is all that useful, though, as the larger p is, the larger b - a can be and the more cases are left open.

Title: Re: Factorial Equation
Post by Sir Col on Mar 28^th, 2005, 8:04am

It looks like we're the only two making any progress on this problem, Tim. Unfortunatley I think that I've managed to reduce it to an unsolved problem in number theory; which does excuse us slightly.

For completeness I'll summarise all of my findings so far in this thread, with what appears to be a rather distressing discovery...

W.L.O.G. let us assume that b<=a.

If b = a, we get (a!)² = 2(a!)+c², (a!)²-2(a!)+1 = c²+1, (a!-1)² = c²+1.

As there is no square one more than another square, we deduce that b<a.

Dividing through by b!:
a! = a!/b! + 1 + c²/b!

As both sides are integer, RHS>=2, so a!>=2, and we deduce that both sides are even. In which case exactly one of a!/b! or c²/b! must be odd, or both non-integer but adding to an odd integral amount [I'd missed this before, and you're not going to like the conclusion!].

(i) Assuming that a!/b! is odd.
This can only happen if a=b or a is odd and b=a-1, but we have already discounted the first possibility.
Therefore, a! = a+1+c²/(a-1)!
(a!)² = a!(a+1)+ac²
(a!)²-(a+1)a! = ac²
(a!-(a+1)/2)² = ac²+((a+1)/2)²
As a is odd, we have an equation with integers throughout: (a!-x)² = ac²+x².

(ii) Alternatively c²/b! is odd.
If b=c, we get a! = a!/c!+1+c²/c!. But c²/c!<1 when c>=4, hence c<=3.
When c=1, a! = a!+2. No solution.
When c=2, c²/c! is even.
When c=3, c²/c! is not integer.
So the other possibility for c²/b! being odd is b<c.
If b=1, a! = a!+1+c², c²+1 = 0. No solution.
So b>=2, in which case b! is even, and for c²/b! to be (odd) integer, c² must be even.

(iii) a!/b! and c²/b! are non-integer, but add to an odd integral amount.
In which case a!+c²=2k, where k is odd; that is, congruent with 2 mod 4.
As a! is even, c² must be even and will be congruent with 0 mod 4.
But for a>=4, a!+c²==0 mod 4.
Hence a=2 or a=3.
The original equation gives,
2 = 2/b! + 1 + c²/b!
b! = c² + 2
Sadly this seems to relate to an an unsolved problem (see below). Similarly, a=3 leads to 5b! = c²+6, which appears equally problematic.

In other words, any other solutions reduce to the following cases:
(i) a!/b! is odd, a is odd and b=a-1. Leading to the equation: (a!-(a+1)/2)² = ac²+((a+1)/2)².
(ii) c²/b! is odd, 1<b<c and c is even.
(iii) a!/b! and c²/b! are non-integer but add to an odd integral amount. This leads to the equation: b! = c² + 2.

Unfortunately the equation in (iii) seems to be a currently unsolved problem in number theory.
http://mathworld.wolfram.com/BrocardsProblem.html

Bother! :(

[e]Edited to remove stupid oversight![/e]

Title: Re: Factorial Equation
Post by Barukh on Mar 28^th, 2005, 9:44am

on 03/28/05 at 08:04:09, Sir Col wrote:

It looks like we're the only two making any progress on this problem, Tim.

…but not the only two keeping an eye on the progress! ;)

Quote:

Unfortunately the equation in (iii) seems to be a currently unsolved problem in number theory.
http://mathworld.wolfram.com/BrocardsProblem.html

Well, that’s not exactly the problem stated by Brocard: the constant is different, and this seems to be crucial: it’s not a perfect square. In the following paper (http://www.math.uiuc.edu/~berndt/articles/galway.pdf) referenced from your link, the authors speak about the result obtained by A. Dabrowski almost a decade ago: it’s about the equation a! + k = c², where k is not a perfect square. I just wonder whether the author assumed k to be positive…

Title: Re: Factorial Equation
Post by Eigenray on Mar 28^th, 2005, 2:02pm

on 03/28/05 at 08:04:09, Sir Col wrote:

(i) Assuming that a!/b! is odd.
This can only happen if a=b or a is odd and b=a-1, but we have already discounted the first possibility.
Therefore, a! = a+1+c²/(a-1)!

Writing a=2k+1, we have
(2k+1)! = 2k+2+c²/(2k)!.
Using TimMann's idea, by [link=http://mathworld.wolfram.com/BertrandsPostulate.html]Bertrand[/link], for k+1>3, there is a prime p with k+1<p<2k, so
k+1 < p < 2k < 2k+2 < 2p.
Now p divides the LHS, and divides (2k)! exactly once, so divides c²/(2k)! an odd (hence non-zero) number of times. But p doesn't divide 2k+2. So this case seems impossible for a=2k+1 > 5.

Quote:

(iii) a!/b! and c²/b! are non-integer, but add to an odd integral amount.

Aren't you assuming b<a?

Title: Re: Factorial Equation
Post by Sir Col on Mar 28^th, 2005, 3:31pm

I got so caught up with modulo arithmetic of squares that I lost sight of something so simple: a!/b! must be integer if b<a. Duh! :-[

Bravo, Eigenray! What a lovely insight and extension of Tim's idea to discount the case of a!/b! being odd and a>5. Of course, the only other cases are: a=5, b=a-1=4, which reduces to c² = 2736 (no solution); a=3, b=2, reduces to c² = 4, which is the solution already obtained.

It seems that the only thing to do now is to show that c²/b! being odd leads to no more solutions; we know that 1<b<c and c is even.

Title: Re: Factorial Equation
Post by SWF on Mar 28^th, 2005, 6:59pm

I gave up on on this one back when it was in the Easy section. In case this of any help, here are a couple of things I tried without success (with b<a, since they can't be equal):

a!*(b!-1) = b! + c²
When b>2 this implies c² = (b!-2) mod (b!-1), I used this to computationally show there is no solution for b=4, 5, 6, 7, 8, 9, 10, 11, or 12, and perhaps somebody can do something more with it. Using a different method it was relatively easy to show that there is no solution for b=3 and the only solution for b=2, occurs with a=3.

I seem to recall being able to show that b cannot equal a-1, but am not sure.

From c² = b!*( a! - 1 - (b+1)*(b+2)*...*(a) ) a number of things may be concluded as others have already described. Any prime, p, occurring to an odd power in the factorization of b! must be a factor of the term in parentheses. Since p is a factor of a!, s = ( 1 + (b+1)*(b+2)*...*(a) ), must be a multiple of p, and therefore a-b<p. As b gets larger there will be many primes between b/2 and b, which would each occur once in the factorization of b!. It seems like a long shot that s could be multiple of all of them, but I haven't been able to prove it.

By the way, b! = c²+2 has no solutions for b>3 because b! equals zero mod 4, but 2+c² cannot be a multiple of 4. Solutions for smaller values of b are are easy to find by doing the arithmetic.

Title: Re: Factorial Equation
Post by Eigenray on Mar 28^th, 2005, 11:17pm

on 03/28/05 at 18:59:26, SWF wrote:

a!*(b!-1) = b! + c²
When b>2 this implies c² = (b!-2) mod (b!-1)

Hmm... actually, I think that does it:
(a!-1)(b!-1) = c²+1
We can't have a prime p | c²+1 with [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?action=display;board=riddles_easy;num=1078017611;start=0#8]p=3 mod 4[/link]. Therefore, if a>3, then a!-1 = 3 mod 4 gives a contradiction. Now the cases b<a<=3 are easily checked.

Title: Re: Factorial Equation
Post by Sir Col on Mar 29^th, 2005, 1:58am

Incredible! How do you remember all these lovely results, Eigenray? :o

I can't believe that the whole problem has reduced to something as simple as this, albeit a non-trivial result. For completeness, and for those that didn't follow that thread at the time...

c²==-1 mod p iff (-1)^(p-1)/2==1 mod p (Euler's criterion).

If p==3 mod 4, then (p-1)/2==1 mod 4; that is, (p-1)/2 will be odd, so -1^(p-1)/2==-1 mod p.

Hence there exists no prime, p==3 mod 4, for which c²==-1 mod p, or c²+1==0 mod p.

Then as Eigenray explained, for a>3, a!==0 mod 4, so a!-1==3 mod 4. That is, a prime, p==3 mod 4 divides LHS, but no prime of that form can divide RHS. Then checking cases a<=3 reveals the unique result.

Well played, Eigenray. And thanks, SWF, for sharing your insight that inspired him. I'll finally get a good night sleep now. ;)