"Surprise!" said c

a ! b ! = a ! + b ! + c 2 \displaystyle \large a!b! = a! + b! + c^2

Positive integers a a , b b , and c c , with a > b a > b , are the unique solution to the equation above.

If a b c = m n \dfrac {a^b}{c} = \dfrac mn for coprime positive integers m m and n n , find m + n m + n .


The answer is 11.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Zach Abueg
Jun 29, 2017

Without loss of generality, let's assume that b a b \leq a .

If b = a b = a , then ( a ! ) 2 = 2 a ! + c 2 \displaystyle (a!)^2 = 2a! + c^2 .

( a ! ) 2 2 a ! + 1 = c 2 + 1 ( a ! 1 ) 2 = c 2 + 1 \displaystyle \begin{aligned} \therefore (a!)^2 - 2a! + 1 & = c^2 + 1 \\ (a! - 1)^2 & = c^2 + 1 \end{aligned}

Note that c > 0 c 2 > 0 c > 0 \implies c^2 > 0 . Since there exists no positive square which is one more than another positive square, we have b < a b < a .

Also, b 1 b \neq 1 - otherwise, a ! = a ! + 1 + c 2 c 2 = 1 a! = a! + 1 + c^2 \implies c^2 = -1 .

Dividing a ! b ! = a ! + b ! + c 2 a!b! = a! + b! + c^2 by b ! b! we have

a ! = a ! b ! + 1 + c 2 b ! \displaystyle a! = \frac{a!}{b!} + 1 + \frac{c^2}{b!}

Clearly the LHS is an integer, so since a ! b ! \displaystyle \frac{a!}{b!} is an integer, c 2 b ! \displaystyle \frac{c^2}{b!} must also be an integer. Furthermore, the RHS 3 \geq 3 , which means that a ! 3 a 3 a! \geq 3 \implies a \geq 3 .

From a ! b ! = a ! + b ! + c 2 a!b! = a! + b! + c^2 , we have a ! b ! a ! b ! + 1 = c 2 + 1 a!b! - a! - b! + 1 = c^2 + 1

( a ! 1 ) ( b ! 1 ) = c 2 + 1 \displaystyle \therefore (a! - 1)(b! - 1) = c^2 + 1

Let us assume that a prime p 3 ( m o d 4 ) p \equiv 3 \pmod{4} divides the RHS.

If c 2 + 1 0 ( m o d p ) c^2 + 1 \equiv 0 \pmod{p} , it follows that c 2 1 ( m o d p ) c^2 \equiv -1 \pmod{p} , and it is clear that p ∤ c p \ \not \mid\ c .

( c 2 ) p 1 2 = c p 1 ( 1 ) p 1 2 ( m o d p ) \displaystyle \therefore (c^2)^{\frac{p - 1}{2}} = c^{p - 1} \equiv (- 1)^{\frac{p - 1}{2}} \pmod{p}

But we are given that p 3 ( m o d 4 ) p \equiv 3 \pmod{4} , so p 1 2 ( m o d 4 ) p - 1 \equiv 2 \pmod{4} , which means that p 1 2 \displaystyle \frac{p - 1}{2} will be odd, and ( 1 ) p 1 2 = 1 \displaystyle (- 1)^{\frac{p - 1}{2}} = - 1 .

So c p 1 1 ( m o d p ) c^{p - 1} \equiv - 1 \pmod{p} , but that is a contradiction since gcd ( c , p ) = 1 \gcd(c, p) = 1 , and by Fermat's Little Theorem , c p 1 1 ( m o d p ) c^{p - 1} \equiv 1 \pmod{p} .

In other words, there exists no prime p 3 ( m o d 4 ) c 2 + 1 p \equiv 3 \pmod{4} \ | \ c^2 + 1 .

However, for a 4 a \geq 4 , a ! 0 ( m o d 4 ) a! \equiv 0 \pmod{4} , and a ! 1 3 ( m o d 4 ) a! - 1 \equiv 3 \pmod{4} ; that is, the LHS is divisible by a prime p 3 ( m o d 4 ) p \equiv 3 \pmod{4} .

Hence, 1 < b < a 3 1 < b < a \leq 3 , but we have already established that a 3 a \geq 3 , so we have a = 3 a = 3 and b = 2 b = 2 , and from the original equation, c = 2 c = 2 .

a b c = 9 2 \displaystyle \implies \frac{a^b}{c} = \frac 92

m + n = 11 \implies m + n = 11

@Calvin Lin Is there a better way to type "does not divide" in Latex than "\not|"?

Zach Abueg - 3 years, 11 months ago

Log in to reply

Nope, that's just it.

I typically use "\mid" for |, which produces \mid . So "\not \mid" will be ∤ \not \mid . Compare against "\not |" which is ∤ \not | .

Calvin Lin Staff - 3 years, 11 months ago

Note: There is a square that is one more than another square. IE 1 and 0.

Calvin Lin Staff - 3 years, 11 months ago

Log in to reply

Edited to include only positive squares. Thanks for pointing it out!

Zach Abueg - 3 years, 11 months ago

Log in to reply

This would be personal preference in terms of solution writing. I would not deal with the a = b a= b or b = 1 b = 1 case at the start because they do not generate insight to help guide / restrict the rest of the solution. (Yes, I understand that you might have approached this problem by trying specific cases at the start.)

Seems to me that the important steps are
1. WLOG a b a \geq b . Divide by b ! b! to conclude that a 3 a \geq 3 .
2. Factorize ( a ! 1 ) ( b ! 1 ) = c 2 + 1 ( a! - 1) ( b! - 1) = c^2 + 1 to conclude that a < 4 a < 4 . Hence a = 3 a =3 .
3. Check b = 1 , 2 , 3 b = 1, 2, 3 .

Calvin Lin Staff - 3 years, 11 months ago

Log in to reply

@Calvin Lin Very straight to the point, I agree. I'll think about that the next time I write a solution. Thanks Calvin!

Zach Abueg - 3 years, 11 months ago

In the puzzle a

Áron Bán-Szabó - 3 years, 11 months ago

Log in to reply

In the puzzle you mentioned that a>b, but I think it would be more interesting, if a=b is possible too.

Áron Bán-Szabó - 3 years, 11 months ago

Doesn't the puzzle say that a > b a>b ?

Janardhanan Sivaramakrishnan - 3 years, 11 months ago

W e h a v e f = a ! b ! ( a ! + ! b ) c 2 = 0 S i n c e a > b , m i n i m u m a = 2 a n d b = 1. B u t i f b = 1 , f = c 2 , s o c = 0. B u t g i v e n c > 0. S o m i n i m u m b = 2 , a n d a > 2. I f a = 3 , a n d b = 2 , f = 6 2 ( 6 + 2 ) c 2 = 4 c 2 = 0. S o c = ± 2. B u t c > 0. S o c = 2. m n = 3 2 2 . m + n = 9 + 2 = 11. We~ have~~~ f=a!*b! - (a!+!b) -c^2=0\\ Since~ a>b, ~~minimum~ a=2~ and~ b=1.\\ But~ if~ b=1,~~~ f=-c^2 , ~~so~c=0.~But~ given~ c>0. \\ So~ minimum ~b=2,~and~~ a>2. \\ If~ a=3,~~and ~b=2,~~~ f=6*2~-~(6~+~2)~-~c^2~=~4~-~c^2=0.\\ So~ ~c=\pm 2.~~ But ~c>0.~~~ So~ c=2.\\ \dfrac m n~=~\dfrac {3^2} 2.\\ \therefore~~ m~+~n~=~9~+~2=\color{#D61F06}{11}.

Interesting use of the conditions to quickly get to the answer!

If it was not given that ( a , b , c ) = ( 3 , 2 , 2 ) (a, b, c) = (3, 2, 2) is the unique solution to this problem, how would you approach it then?

Zach Abueg - 3 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...