# 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 *) 
Answer
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 
Answer
2 years ago
 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) 
Answer
2 years ago
 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 ;)
Answer
2 years ago
 - another post of yours has been selected for the Staff Picks group, congratulations !We are happy to see you at the tops of the "Featured Contributor" board. Thank you for your wonderful contributions, and please keep them coming!
Answer
2 years ago