# Number Theory Problem in 2012 CMO (created on Wolfram Cloud)

GROUPS:
 Shenghui Yang 7 Votes You can view the blog on this static page generated by Wolfram Cloud (no beta now!) Question: Given two positive integers a and b. The two numbers satisfy the following conditions: $a - b$ is a prime number $p$ and $a \times b$ is a perfect square $n^2$ . Find the smallest value of $a$ no less than $2012$. Let's solve it The formula of those conditions mentioned in the problem is quite straightforward:  a - b == p (* prime *) a * b == n^2 a >= 2012 && a >= b Use the deduction to reduce the problem to known solving techniques such as Diophantine equation or Pell equation. To use the first condition in the second relation, I'd better create a certain type of factorization so that $a - b$ can be taken out. This usually useful with prime number $p$ because that $p$ divides $x \times y$ implies $p$ is either a divisor of $x$ or $y$.  Factor[a*b-b^2] (* (a-b)*b *) Factor[n^2-b^2] (* (n-b)(n+b) *) We know that the prime $p = a - b$ cannot divide either $a$ or $b$. Otherwise, let $b = k \times p$ and $a = (k+1) \times p$, $a \times b = k \times (k+1) \times p^2$ is never a perfect square unless $k = 0$. Therefore only one term here can be a multiplier of p: either $n - b$ or $n + b$ (aka the product cannot produce $p^2$, $p^3$ and so on). Assume $p$ divides $n - b$, or $n - b = \lambda \times (a-b)$ for $\lambda$ being a positive integer.  Reduce[(a-b)*b==(n+b)*\[Lambda]*(a-b)&&n>0&&a>b>0 && \[Lambda]>0,b,Integers] (* or b = \[Lambda] (n+b) > b ==> False*) (* False *) The other statement must be true: $n + b = \lambda (a-b)$. The following code shows that the solution is possible  Simplify/@Reduce[(a-b)*b==(n-b)*\[Lambda]*(a-b)&&a>n>b>1 && \[Lambda]>0,{n},Integers] Note that n must be an integer and b is an integer, [Lambda] must divide b in order to make b + b/[Lambda] an integer. Therefore $b = k * \lambda$ for some positive integer $k$.  eqn=n + b == \[Lambda] (a-b)/.{n->k+k*\[Lambda],b->k*\[Lambda]} Reduce[eqn&&\[Lambda]>= 1,a,Integers] Factor[%[[-1]]] Because $\lambda$ and $\lambda+1$ are co-prime, $\lambda$ divides k. In case $k == \lambda$, a itself is a perfect square. Lets have a try:  Reduce[(1+\[Lambda])^2 >=2012&&\[Lambda]>0,\[Lambda], Integers] Therefore,  a/.{a->45^2} (* = 2025 *) b/.{b->44^2} (* = 1936 *) Check if the choice pass the prime test and square test:  Block[{a=45^2,b=44^2},{PrimeQ[a-b],IntegerQ[Sqrt[a*b]]}] (* { True, True} *) So we know the upper bound of the solution is $a = 2025$. Is there any other possibility between $2012$ and $2025$ ? Well we may use the brutal force method here without too much pain:  candidates=Table[{a,ToRules[#]&/@Reduce[a==k(1+\[Lambda])^2/\[Lambda]&&k>= \[Lambda]>1,{k,\[Lambda]},Integers]},{a,2012,2025}] Grid[{{"Value of a ", "Solution"}}~Join~candidates,Alignment->{{Left,Center}},Dividers->True] I can reject $a = 2016$ immediately because none of the $b = \lambda*k$ produce an odd number. Otherwise, $a - b$ must be prime and even, which is $2$.  Reduce[a(a-2)==n^2&&a>1,{a,n},Integers] (* a == 2 && n == 0 *)  $a = 2023$ is rejected because the prime test is failed:  PrimeQ[2023-16*112] (* False *) 
2 years ago
4 Replies
 Sander Huisman 1 Vote Great explanation! How about finding integer solutions for a, b, and c that satisfy: a^3 + b^3 + c^3 == 33 
 Shenghui Yang 1 Vote The moment I see your question my gut feeling tells me there must be no trivial solution. I searched on the Mathworld page of Diophantine Equation -- 3rd Powers and found the reference paper J.C.P. Miller & M.F.C. Woollett, Solutions of the Diophantine equation x3 + y3 + z3 = k, J. London Math. Soc. 30 (1955), 101–110. There are two other articles reference the same source. Rowland, Known Families of Integer Solutions of x3 + y3 + z3 = n Heath-Brown, On Solving The Diophantine Equation X3 +Y3 +Z3 = K On A Vector Computer In your case, there is no known solution yet according to Heath-Brown. Mathematica can found the following solution with some hint: In[5]:= Reduce[a^3+b^3+(-159380)^3==39,{a,b},Integers] Out[5]= (a==117367&&b==134476)||(a==134476&&b==117367) 
 There isn't, they checked a,b,c up to 10^14 in some clever way. (10 months CPU time (2007)). a^3 +b^3 + c^3 == n where n \[Element] {33, 42, 74, 114, 165, 390, 579, 627, 633, 732, 795, 906, 921, 975} are not solved yet! I would love to bruteforce it (using Mathematica) up to 10^15, to --perhaps-- eliminate some of them. Maybe you have some parallel computing power left over ;)