Message Boards Message Boards

8
|
9930 Views
|
4 Replies
|
10 Total Likes
View groups...
Share
Share this post:

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

Posted 8 years ago

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]]]

res

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]

result

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 *)
POSTED BY: Shenghui Yang
4 Replies

enter image description here - 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!

POSTED BY: Moderation Team

Great explanation! How about finding integer solutions for a, b, and c that satisfy:

a^3 + b^3 + c^3 == 33
POSTED BY: Sander Huisman

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)
POSTED BY: Shenghui Yang

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 ;)

POSTED BY: Sander Huisman
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract