Re: Challenge problem

*To*: mathgroup at smc.vnet.net*Subject*: [mg71225] Re: [mg71123] Challenge problem*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Fri, 10 Nov 2006 06:39:04 -0500 (EST)*References*: <200611090837.DAA15514@smc.vnet.net>

On 9 Nov 2006, at 17:37, Coleman, Mark wrote: > I recently received the annual newsletter from the Math-Stats > department > of my undergraduate alma mater. In part of the newsletter they > posed the > following challenge problem: > > "For which rational numbers q is 3q^3 + 10q^2 + 3q an integer?" > > The problem comes from an annual mathematics competition the school > sponsors. I fumbled around a bit, using Mathematica v5.2 to > attempt an answer, > but without much luck. Of course I'm a statistician, not an algebraist > :-). But my curiosity is now piqued and I was wondering if someone > might > outline an elegant answer using Mathematica. > > Thanks, > > -Mark > I think I can prove that the answer consists of fractions of the form (9 n + 8)/3, where n is any integers. Indeed, you can check that these work as follows: eq = 3q^3 + 10q^2 + 3q; Simplify[eq /. q -> (9*n + 8)/3] 81*n^3 + 306*n^2 + 361*n + 136 Unfortunately proof that no other expressions work makes no use of Mathematica at all. I doubt that such a proof can be found but who knows, I have seen more surprising things proved by means of computer algebra systems. Anyway, here goes an elementary proof, with only a slight use of Mathematica to justify posting it here. Assume that we have a solution of the form m/n where m and n are relatively prime. Now, look at the expression: Factor[Together[3*q^3 + 10*q^2 + 3*q /. q -> m/n]] (m*(3*m + n)*(m + 3*n))/n^3 Suppose that p is a prime that divides n, hence it has to divide the numerator. It can's divide m by assumption. It can't also divide m + 3*n for the same reason. So it has t divide 3*m +n, and since it does not divide m it has to be 3. So n must be a power of 3. So suppose n = 3^s. It is easy to see that we must have s=1. So our fraction must have n=3. The expression now takes the form (1/9)*m*(m + 1)*(m + 9) So m*(m + 1)*(m + 9) must be divisible by 9. Now m and m+9 are not divisible by 3, so m+1 must be divisible by 9, which means m is of the form 9k-1, which is the same as 9l +8. Andrzej Kozlowski

**References**:**Challenge problem***From:*"Coleman, Mark" <Mark.Coleman@LibertyMutual.com>