Mathematical Excalibur, Volume 15, Number 4

Abstract

Mathematical Excalibur Volume 15, Number 4 January 2011 Klamkin’s Inequality Kin Y. Li Olympiad Corner Below are the problems of the 2011 Chinese Math Olympiad, which was held on January 2011. Problem 1. Let a1,a2,…,an (n≥3) be real numbers. Prove that where , max , min , [x] denotes the greatest integer not exceeding x. Problem 2. In the figure, D is the midpoint of the arc BC on the circumcircle Γ of triangle ABC. Point X is on arc BD. E is the midpoint of arc AX. S is a point on arc AC. Lines SD and BC intersect at point R. Lines SE and AX intersect at point T. Prove that if RT || DE, then the incenter of triangle ABC is on line RT. A B C D E X S R T (continued on page 4) Editors: 張 百 康 (CHEUNG Pak-Hong), Munsang College, HK 高 子 眉 (KO Tsz-Mei) 梁 達 榮 (LEUNG Tat-Wing) 李 健 賢 (LI Kin-Yin), Dept. of Math., HKUST 吳 鏡 波 (NG Keng-Po Roger), ITC, HKPU Artist: 楊 秀 英 (YEUNG Sau-Ying Camille), MFA, CU Acknowledgment: Thanks to Elina Chiu, Math. Dept., HKUST for general assistance. On-line: http://www.math.ust.hk/mathematical_excalibur/ The editors welcome contributions from all teachers and students. With your submission, please include your name, address, school, email, telephone and fax numbers (if available). Electronic submissions, especially in MS Word, are encouraged. The deadline for receiving material for the next issue is February 28, 2011. For individual subscription for the next five issues for the 09-10 academic year, send us five stamped self-addressed envelopes. Send all correspondence to: Dr. Kin-Yin LI, Math Dept., Hong Kong Univ. of Science and Technology, Clear Water Bay, Kowloon, Hong Kong Fax: (852) 2358 1643 Email: makyli@ust.hk © Department of Mathematics, The Hong Kong University of Science and Technology In 1971 Professor Murray Klamkin established the following Theorem. For any real numbers x,y,z, integer n and angles α,β,γ of any triangle, we have ( 1) 12( cos cos cos ). 2 2 2 yz nα zx nβ xy nγ Equality holds if and only if sin α sin β sin nγ The proof follows immediately from expanding ( )2 x + (−1)n ( y cos nγ + z cos nβ ) There are many nice inequalities that we can obtain from this inequality. The following are some examples (see references [1] and [2] for more). Example 1. For angles α,β,γ of any triangle, if n is an odd integer, then cosnα + cosnβ + cosnγ ≤ 3/ 2. If n is an even integer, then cosnα + cosnβ + cosnγ ≥ −3/ 2. (This is just the case x=y=z=1.) Example 2. For angles α,β,γ of any triangle, 3 cosα + 2cosβ + 2 3 cosγ ≤ 4. (This is just the case n = 1, x = sin 90°, y = sin 60°, z = sin 30°.) There are many symmetric inequalities in α,β,γ, which can be proved by standard identities or methods. However, if we encounter asymmetric inequality like the one in example 2, it may be puzzling in coming up with a proof. Example 3. Let a,b,c be sides of a triangle with area Δ. If r,s,t are any real numbers, then prove that

Solution. Let α,β,γ be the angles of the triangle. We first observe that 4Δ2 = a2b2 sin2γ =b2c2 sin2α =c2a2 sin2β and cos 2θ = 1−2sin2 θ. So we can try to set n = 2, x=ar, y=bs, z=ct. Indeed, after applying Klamkin’s inequality, we get the result. Example 4. Let a,b,c be sides of a triangle with area Δ. Prove that

Comment: It may seem that we can use example 3 by setting r=a, s=b, t=c, but unfortunately holds only when a=b=c by the AM-GM inequality. Solution. To solve this one, we bring in the circumradius R of the triangle. We recall that 2Δ=bcsin α and by extended sine law, 2R=a/(sin α). So 4ΔR=abc. Now we set r=bcx, s=cay and t=abz. Then the inequality in example 3 becomes (x + y + z)2R2 ≥ yza2 + zxb2 + xyc2. (*) Next, we set yz=1/b2, zx=1/c2, xy=1/a2, from which we can solve for x,y,z to get Then (*) becomes Mathematical Excalibur, Vol. 15, No. 4, Jan. 11 Page 2 Example 5. (1998 Korean Math Olympiad) Postive real numbers a,b,c satisfy a+b+c=abc. Prove that and determine when equality holds. Solution. Let a = tan u, b = tan v and c = t an w, where u,v,w > 0. As a+b+c=abc, tan u+tan v+tan w = tan u tan v tan w, which can be written as tan( ). 1 tan tan tan tan tan v w v w u v w = + This implies u+v+w=nπ for some odd positive integer n. Let α = u/n, β = v/n and γ = w/n. Taking x = y = z = 1 in Klamkin’s inequality (as in example 1), we have cosnα + cosnβ + cosnγ ≤ 3/ 2, which is the desired inequality. Equality holds if and only if a = b = c = 3. For the next two examples, we will introduce the following Fact: Three positive real numbers x,y,z satisfy the equation x2+y2+z2+xyz = 4 (**) if and only if there exists an acute triangle with angles α,β,γ such that x = 2cos α, y = 2cos β, z = 2cos γ. Proof. If x,y,z > 0 and x2+y2+z2+xyz = 4, then x2, y2, z2 < 4. So 0 < x, y, z < 2. Hence, there are positive α,β,γ < π/2 such that x = 2cos α, y = 2cos β and z = 2cos γ. Substituting these into (**) and simplifying, we get cos γ = −cos (α+β), which implies α+β+ γ = π. We can get the converse by using trigonometric identities. Example 6. (1995 IMO Shortlisted Problem) Let a,b,c be positive real numbers. Determine all positive real numbers x,y,z satisfying the system of equations x+y+z = a+b+c, 4xyz−(a2x+b2y+c2z) = abc. Solution. We can rewrite the second equation as 4. xyz abc xy c zx b yz a By the fact, there exists an acute triangle with angles α,β,γ such that = 2cosα, = 2cosβ , = 2cosγ . Then the first equation becomes x + y + z = 2( yzcosα + zxcosβ + xycosγ ). This is the equality case of Klamkin’s inequality. So sinα sinβ sinγ x = y = z As γ+β = π−α, so sin(γ+β)/sin α=1. Then cosβ cosγ sin sin cos sin cos = γ β β γ So x = (b+c)/2. Similarly, y = (c+a)/2 and z = (a+b)/2. Example 7. (2007 IMO Chinese Team Training Test) Positive real numbers u,v,w satisfy the equation u + v + w + uvw = 4. Prove that Solution. By the fact, there exists an acute triangle with angles α,β,γ such that u = 2cosα , v = 2cosβ , w = 2cosγ . The desired inequality becomes cos 2cos cos cos 2cos cos cos 2cos cos ≥ 4(cos2α + cos2 β + cos2γ ). Comparing with Klamkin’s inequality, all we have to do is to take n = 1 and cos 2cos cos cos 2cos cos y = 2cos cos Example 8. (1988 IMO Shortlisted Problem) Let n be an integer greater than 1. For i=1,2,…,n, αi > 0, βi > 0 and Prove that cot . sin cos Solution. For n = 2, we have equality sin cos 1 2 = = α + α For n = 3, α1, α2, α3 are angles of a triangle, say with opposite sides a,b,c. Let Δ be the area of the triangle. Now 2Δ = bcsin α1 = casin α2 = absin α3. Combining with the cosine law, we get cot cos and similarly for cot α2 and cot α3. By Klamkin’s inequality, 2( cos cos cos ) sin 4 cos Cancelling 4Δ, we will finish the case n = 3. For the case n > 3, suppose the case n−1 is true. We have cos sin

This finishes the induction. References [1] M.S.Klamkin, “Asymetric Triangle Inequalities,” Publ.Elektrotehn. Fak. Ser. Mat. Fiz. Univ. Beograd, No. 357-380 (1971) pp. 33-44. [2] Zhu Hua-Wei, From Mathematical Competitions to Competition Mathematics, Science Press, 2009 (in Chinese). Mathematical Excalibur, Vol. 15, No. 4, Jan. 11 Page 3 Problem Corner We welcome readers to submit their solutions to the problems posed below for publication consideration. The solutions should be preceded by the solver’s name, home (or email) address and school affiliation. Please send submissions to Dr. Kin Y. Li, Department of Mathematics, The Hong Kong University of Science & Technology, Clear Water Bay, Kowloon, Hong Kong. The deadline for sending solutions is February 28, 2011. Problem 361. Among all real numbers a and b satisfying the property that the equation x4+ax3+bx2+ax+1=0 has a real root, determine the minimum possible value of a2+b2 with proof. Problem 362. Determine all positive rational numbers x,y,z such that are integers. Problem 363. Extend side CB of triangle ABC beyond B to a point D such that DB=AB. Let M be the midpoint of side AC. Let the bisector of ∠ABC intersect line DM at P. Prove that ∠BAP =∠ACB. Problem 364. Eleven robbers own a treasure box. What is the least number of locks they can put on the box so that there is a way to distribute the keys of the locks to the eleven robbers with no five of them can open all the locks, but every six of them can open all the locks? The robbers agree to make enough duplicate keys of the locks for this plan to work. Problem 365. For nonnegative real numbers a,b,c satisfying ab+bc+ca = 1, prove that

Solutions

Problem 356. A and B alternately color points on an initially colorless plane as follow. A plays first. When A takes his turn, he will choose a point not yet colored and paint it red. When B takes his turn, he will choose 2010 points not yet colored and paint them blue. When the plane contains three red points that are the vertices of an equilateral triangle, then A wins. Following the rules of the game, can B stop A from winning Solution. LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College), Anna PUN Ying (HKU Math) and The 7B Mathematics Group (Carmel Alison Lam Foundation Secondary School). The answer is negative. In the first 2n moves, A can color n red points on a line, while B can color 2010n blue points. For each pair of the n red points A colored, there are two points (on the perpendicular bisector of the pair) that can be chosen as vertices for making equilateral triangles with the pair. When n > 2011, we have ( 1) 2010 . Then B cannot stop A from winning. Other commended solvers: King’s College Problem Solving Team (Angus CHUNG, Raymond LO, Benjamin LUI), Andy LOO (St. Paul’s Co-ed College),Emanuele NATALE (Università di Roma “Tor Vergata”, Roma, Italy) and Lorenzo PASCALI (Università di Roma “La Sapienza”, Roma, Italy), WONG Sze Nga (Diocesan Girls’ School). Problem 357. Prove that for every positive integer n, there do not exist four integers a, b, c, d such that ad=bc and n2 < Solution. U. BATZORIG (National University of Mongolia) and LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College). We first prove a useful Fact (Four Number Theorem): Let a,b,c,d be positive integers with ad=bc, then there exists positive integers p,q,r,s such that a=pq, b=qr, c=ps, d=rs. To see this, let p=gcd(a,c), then p|a and p|c. So q=a/p and s=c/p are positive integers. Now p=gcd(a,c) implies gcd(q,s)=1. From ad=bc, we get qd=sb. Then s|d. So r=d/s is a positive integer and a=pq, b=qr, c=ps, d=rs. For the problem, assume a,b,c,d exist as required. Applying the fact, since d > b > a, we get s>q and r>p. Then s≥q+1, r≥p+1 and we get d = rs ≥ (p +1)(q +1) ≥ ( pq +1)2 = ( a +1)2 > (n +1)2 , a contradiction. Other commended solvers: King’s College Problem Solving Team (Angus CHUNG, Raymond LO, Benjamin LUI), Anna PUN Ying (HKU Math), The 7B Mathematics Group (Carmel Alison Lam Foundation Secondary School) and WONG Sze Nga (Diocesan Girls’ School). Problem 358. ABCD is a cyclic quadrilateral with AC intersects BD at P. Let E, F, G, H be the feet of perpendiculars from P to sides AB, BC, CD, DA respectively. Prove that lines EH, BD, FG are concurrent or are parallel. Solution. U. BATZORIG (National University of Mongolia), King’s College Problem Solving Team (Angus CHUNG, Raymond LO, Benjamin LUI), Abby LEE Shing Chi (SKH Lam Woo Memorial Secondary School), LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College), Anna PUN Ying (HKU Math), Anderson TORRES (São Paulo, Brazil) and WONG Sze Nga (Diocesan Girls’ School). D C Since ABCD is cyclic, ∠BAC =∠CDB and ∠ABD =∠DCA, which imply ΔAPB and ΔDPC are similar. As E and G are feet of perpendiculars from P to these triangles (and similarity implies the corresponding segments of triangles are proportional), we get AE/EB=DG/GC. Similarly, we get AH/HD=BF/FC. If EH || BD, then AE/EB = AH/HD, which is equivalent to DG/GC=BF/FC, and hence FG || BD. Otherwise, lines EH and BD intersect at some point I. By Menelaus theorem and its converse, we have HA DH ID BI EB AE which is equivalent to Mathematical Excalibur, Vol. 15, No. 4, Jan. 11 Page 4 FB CF GC DG ID BI and lines BD and FG also intersect at I. Other commended solvers: Lorenzo PASCALI (Università di Roma “La Sapienza”, Roma, Italy). Problem 359. (Due to Michel BATAILLE) Determine (with proof) all real numbers x,y,z such that x+y+z ≥ 3 and x3 + y3 + z3 + x4 + y4 + z4 ≤2(x2 + y2 + z2). Solution. LI Pak Hin (PLK Vicwood K. T. Chong Sixth Form College), Paolo PERFETTI (Math Dept, Università degli studi di Tor Vergata Roma, via della ricerca scientifica, Roma, Italy) and Terence ZHU (Affilated High School of South China Normal University). Let x,y,z be real numbers satisfying the conditions. For all real w, w2+3w+3 ≥ (w+3/2)2 implies (w2+3w+3)(w−1)2 ≥ 0. Expanding, we get (*) w4+w3−2w2 ≥ 3w−3. Applying (*) to w=x,y,z and adding, then using the conditions on x,y,z, we get 0≥x3 +y3 +z3 +x4 +y4 +z4 −2(x2 +y2 +z2) ≥ 3(x + y + z) − 9 ≥ 0. Thus, for such x,y,z, we must have equalities in the (*) inequality for x,y,z. So x = y = z = 1 is the only solution. Comments: For the idea behind this solution, we refer the readers to the article on the tangent line method (see Math Excalibur, vol. 10, no. 5, page 1). For those who do not know this method, we provide the Proposer’s solution. Suppose (x,y,z) is a solution. Let s=x+y+z and S=x2y+y2z +z2x+xy2+yz2+zx2. By expansion, we have s(x2+y2+z2)−S= x3+y3+z3. Hence, s(x2+y2+z2)−S+x4+y4+z4 ≤ 2(x2+y2+z2), which is equivalent to (s−2)(x2+y2+z2)+x4+y4+z4 ≤ S. (*) Since S is the dot product of the vectors v =(x2,y2,z2,x,y,z) and w =(y,z,x,y2,z2,x2), by the Cauchy Schwarz inequality, S ≤ x2+y2+z2+x4+y4+z4 . (**) Combining (*) and (**), we conclude (s−3)(x2+y2+z2) ≤ 0. Since s ≥ 3, we get s=3 and (*) and (**) are equalities. Hence, vectors v and w are scalar multiple of each other. Since x,y,z are not all zeros, simple algebra yields x=y=z=1. This is the only solution. Comments: Some solvers overlooked the possibility that x or y or z may be negative in applying the Cauchy Schwarz inequality! Other commended solvers: U. BATZORIG (National University of Mongolia) and Shaarvdorj (11th High School of UB, Mongolia), King’s College Problem Solving Team (Angus CHUNG, Raymond LO, Benjamin LUI), Thien NGUYEN (Luong The Vinh High School, Dong Nai, Vietnam), Anna PUN Ying (HKU Math), The 7B Mathematics Group (Carmel Alison Lam Foundation Secondary School) and WONG Sze Nga (Diocesan Girls’ School). Problem 360. (Due to Terence ZHU, Affiliated High School of Southern China Normal University) Let n be a positive integer. We call a set S of at least n distinct positive integers a n-divisible set if among every n elements of S, there always exist two of them, one is divisible by the other. Determine the least integer m (in terms of n) such that every n-divisible set S with m elements contains n integers, one of them is divisible by all the remaining n−1 integers. Solution. Anna PUN Ying (HKU Math) and the proposer independently. The smallest m is (n−1)2+1. First choose distinct prime numbers p1, p2, …, pn−1. For from 1 to n−1, let and let A be any nonempty subset of their union. Then A is n-divisible because among every n of the elements, by the pigeonhole principle, two of them will be in the same Ai, then one is divisible by the other. However, among n elements, two of them will also be in different Ai’s and neither one is divisible by the other. So m ≤ (n−1)2 will not work. If m ≥ (n−1)2+1 and S is a n-divisible set with m elements, then let k1 be the largest element in S and let B1 be the subset of S consisted of all the divisors of k1 in S. Let k2 be the largest element in S and not in B1. Let B2 be the subset of S consisted of all the divisors of k2 in S and not in B1. Repeat this to get a partition of S. Assume there are at least n of these Bi set. For i from 1 to n, let ji be the largest element in Bi. However, by the definition of the Bi sets, {j1,j2,…,jn} contradicts the n-divisiblity of S. So there are at most n−1 Bi’s. Since m ≥ (n−1)2+1, one of the Bi must have at least n elements. Then for S, we can choose n elements from this Bi with ki included so that ki is divisible by all the remaining n−1 integers. Therefore, the least m is (n−1)2+1. Other commended solvers: WONG Sze Nga (Diocesan Girls’ School). Olympiad Corner (continued from page 1) Problem 3. Let A be a finite set of real numbers. A1,A2,…,An are nonempty subsets of A satisfying the following conditions: (1) the sum of all elements in A is 0; (2) for every xi∈Ai (i=1,2,…,n), we have x1+x2+⋯+xn > 0. Prove that there exist 1≤i1<i2<⋯<ik ≤ n such that 1 2 A denotes the number of elements in the finite set X. Problem 4. Let n be a positive integer, set S = {1,2,…,n}. For nonempty finite sets A and B of real numbers, find the minimum of |AΔ S|+|BΔ S|+|CΔ S|, where C =A+B ={a+b | a∈A, b∈B}, X ΔY = {x | x belongs to exactly one of X or Y }, |X| denotes the number of elements in the finite set X. Problem 5. Let n ≥ 4 be a given integer. For nonnegative real numbers a1,a2,…,an, b1,b2,…,bn satisfying a1+a2+⋯+an = b1+b2 +⋯+bn > 0, find the maximum of Problem 6. Prove that for every given positive integers m,n, there exist infinitely many pairs of coprime positive integers a,b such that a+b | ama+bnb.

Solutions to Olympiad Corner, vol. 15, no.4 Solutions of the 2011 Chinese Mathematical Olympiad Problem 1. If n=2k (k a positive integer), then t a; - t aj al+1 = l t (a j - aj+1l ~ n (M - m)2. If 1=1 1=1 2 1=1 2 n=2k+ 1 (k a positive integer), then since in every cyclic listing of 2k+ 1 numbers, there always exist three 2k+l 2k+l_ consecutive terms that are monotone (because IT (al -a/-1)(al+1 ~a;) = II (al-al_1)2 ~ 0 implies for 1=1 1=1 some i, ai- ai-1 and ai+1-ai are of the same sign), we may assume a2k, a2k+1, a1 are monotone. Then (a2k - a2k+1)2 + (a2k+1 - a1)2 ~ (a2k - ( 1)2 . Hence, we can reduce the 2k+ 1 case to to the 2k case to get n n 1 n 1 2k-l [n ] La; - Lalal+1 =-2:(al -aI+1)2 ~-(L(al-al+l)2 + (a2k -a1)2) ~ - (M _m)2. 1=1 1=1 2 1=1 2 1=1 - 2 Problem 2. Connect AD. Let AD and RT intersect at 1. Since D is the midpoint of arc BC, so AI is the angle bisector of LBAC. Connect AS, S1. Then since RTIIDE, so LSTI=LSED=LSAL Hence, A,T,I,S are points on some circle COl. Connect CE. Let CE and RT intersect at J. Connect SC. Then LSRJ=LSDE=LSCE. Hence, S,J,R,C are points on some circle CO2. Let COl intersect 0)2 at Sand K. We claim AJ and CI intersect at K. To see this, let COl intersect AJ at A and Kl. Since E is the midpoint of arc AX, LSK1A=LSTA=(arc SA+arc XE)/2=(arc SA+arc AE)/2=LSDE=LSRT=LSRJ. So S, K-1,J,R are concyclic, hence K1 is on CO2. Similarly, let CO2 intersect CI at C and K2. Then 'K~ is on 0)1. Hence, Kl and K2 coincide with K. Since LCAD=LCAI, so LTJE=LCJR=LCED=LCAD. Hence, A,I,J,C are concyclic. Then LACI=LAJI. Also, since C,K,J,R are concyclic, we get LBCI=LICRLAJ1. Then LACI=LBC1. Therefore, I is the incenter of 6.ABC. Problem 3. Let A={a1,' .,am} witha1> .. ·>am. From (1), we get a1+'·+am=O. Consider the least number in every Ai. Among A1, ... ,Am, let ki of them have aj as least number for i=l, ... ,m. Then kl+ .. +km=n and froni (2), klal+ .. ·+kmam>O. For s=1,2, ... ,m-l, there are k1+ .. ·+ks sets with least number at least as. Hence, the_union of these sets is contained in {al, ... ,as} and so has at most s elements. Next, we prove there exists s in {1,2, ... ,m-1} such that k=k1+ ... +ks>snlm. Assume not, then kl+ ... +ks~snlmfor s=1,2, ... ,m -1. Applying Abel's summation by part, we get the contradiction that m - m 0< Lkjaj = L(as - as+1)(k1 + ... + ks) + am(k1 + ... + km)::;; L (as - as+1) sn +(;[mn = ~ Laj = O. j=1 - j=1 s=1 m - m j=1 For this s, take those AI, ... ,An with least number at least as. Let them be A,' , ... , AI . From above, k=kl + ks>sn/m and I All u .. · U Alk I~ s < km / n = k I A I In. Problem 4. The minimum value is n+ 1. First, taking A=B=S, we get IA 6. SI+IB 6. SI+IC 6. SI=n+ 1. Next we show generally k=IA6. SI+IB 6. SI+IC6. SI2':n+ 1. Let X\Y={xl xEX; xE;tY}. Then k=IA\SI+IB\SI+IC\SI + IS\AI+IS\BI+IS\q. It suffices to show (i) IA\SI+IB\SI+IS\q 2': 1 and (ii) IC\SI+IS\AI+IS\BI2': n. Now (i) is clear if IA\SI>O or IB\SI>O. Otherwise, IA\SI=IB\SI~O, then A,BS;S.Hence 1 is not in C. So IS\q2':1. Next, (ii) holds if AnS=0. Otherwise, let n-j be the largest number in AnS, where O::sj ::s n -1. Then IS\AI;:::k. On the other hand, for i=k+l,k+2, ... ,n, either iEtB (that is iES\B) or iEB (then n -k+iEC\S). So IC\SI+IS\BI;:::n-k. Then (li) follows. Problem 5. The maximum value is n~l. Without loss of generality, we may assume al+ ... +an == 1 = bj+ n n +bn. It suffices to show Ial(al +bl ) S; (n-1)Ibl(al +b,). After rearrangement, we can write it as (n -1) I b,2 + (n - 2) I alb, ~ I a,2. By symmetry, we may assume bi is the least among bl,'' ,bn' Then 1=1 1=1 1=1 2 + (1- b1)2 + (n - 2)b1 = nb1 2 +(n - 4)b1 + 1 ~ 1= Ial Ia;. Problem 6. If mn=1, then the result follows. In case mn since na(ama+bnb)=(a+b)na+b+ a[(mn)a it suffices to show there are infinitely many pairs of coprime positive integers a,b such that (a+b,n)=1 and a+b I (mnt - na+b. Let p=a+b. Then, it suffices to show there are infinitely many primes p and integers 1:S a :S p -1 such that p I (mn) By Fermat's little theorem, if we have al=a2 (mod p-1), a then (mnr' == (mnr2 (mod p). Hence, it suffices to show there are infinitely many primes p and positive integers a such that p I (mn)a - n. Assume there are only finitely many such prime p. Let them be PI, P2, '', pro (Since mn2, such prime exists.) Suppose (mn)2 - n = P:' p~2 ... p~r (call this (*)), where ai are nonnegative for 1 :S i :S r. Next define a = p~' p~2 ... p~r (PI -1) .. '(Pr -1) + 2. Suppose (mnt - n = pf'pf2 ... pfr (call this (**)), where ~i are nonnegative for 1 :S i :S r. If Pi I n, then by (* *) and a> 2, we see pri In. Hence, pri I (mn)2 - n . From (*), we see ~i :S ai. If Pi t n, then Pi t m. Hence, (p~i+l, mn) = 1. Observe that rp(p~i+l) = p~1 (PI -1) is a divisor of a-2. By Euler's theorem, we see (mnt -11 == (mn)2 -n(modp~/+l). Since p~/+l t (mn)2 - n, we get, p~/+l t (mnt- n. Hence ~i:S ai. So (mn t - n = pf' pf2 .. ·pfr s; P:' p~2 ... p~r = (mn)2 - n. This leads to a :S 2, a contradiction.