MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020

  • To: mathgroup at smc.vnet.net
  • Subject: [mg122155] Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Sun, 16 Oct 2011 16:45:31 -0400 (EDT)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • References: <j6e693$kef$1@smc.vnet.net> <201110050801.EAA07025@smc.vnet.net> <360851F3-7690-47A6-BC84-E9521100E6F4@mimuw.edu.pl> <A0A54467-5287-4372-9FA6-F0FD865B77D2@mimuw.edu.pl> <84B4CB1D-C8A7-4A5F-8303-9FEC113F7D16@mimuw.edu.pl> <1318773921.12784.YahooMailNeo@web43139.mail.sp1.yahoo.com>

Well, I don't think Reduce can solve it "directly" but here is an easy 
method that makes use of  Reduce and a tiny bit of elementary number 
theory to solve it.

 Let g denote the GCD of a and b. Then we know that a b = 223020 g 
(from the well known relationship between GCD and LCM). Hence we need to 
solve the equation Reduce[{a + b == 5432, a b == 223020 g}, {a, 
b}, Integers] for all possible GCD candidates of a and b. Since the GCD 
of a and b is always a divisor of their sum a+b == 5432 we can 
simply test all possible divisors (there are only 16).

ls = Divisors[5432]

{1,2,4,7,8,14,28,56,97,194,388,679,776,1358,2716,5432}

(Reduce[{a + b == 5432, a*b == 223020*#1}, {a, b}, Integers] & ) 
/@ ls

{False, False, False, False, False, False,
   (a == 1652 && b == 3780) || (a == 3780 && b == 1652), 
False,
   False, False, False, False, False, False, False, False}

Thus we see that the only possibility is that one of the numbers is 1562 
and the other 3780.

Andrzej Kozlowski

On 16 Oct 2011, at 16:05, dimitris anagnostou wrote:

> Hello Mr Kozlowski .
>
> This is from a post of mine to MathGroup that it hasn't appeared yet.
>
> This is taken from the recent book (2010): " Mathematica: A 
Problem-Centered Approach" by R. Hazrat.
>
> "The sum of two positive integers is 5432 and their least common 
multiple is
> 223020. Find the numbers."
>
> A solution:
>
> Do[If[LCM[i, 5432 - i] == 223020, Print[i, "  ", 5432 - i]], {i, 
1,  2718}]
> 1652  3780
>
> I wonder if we can solve the system of equations:
>
> a+b==5432&&LCM[a,b]==223020
>
> using codes that contain built in functions like Reduce.
>
> I guess this is not a trivial one because the so much powerful Reduce 
itself fails
>
> In[1]:= Reduce[{a + b == 5432, LCM[a, b] == 223020}, {a, b}, 
Integers]
>
> During evaluation of In[1]:= Reduce::nsmet:This system cannot be 
solved with the methods available to Reduce. >>
>
> Out[1]= Reduce[{a + b == 5432, LCM[a, b] == 223020}, {a, b}, 
Integers]
>
> I would really appreciate your ideas.
>
> Best Regards
>
> Dimitris Anagnostou
>
> From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
> To: dimitris anagnostou <dimmechan at yahoo.com>
> Cc: Bobby Treat <drBob at bigfoot.com>; Dr. Wolfgang Hintze 
<weh at snafu.de>; "mathgroup at smc.vnet.net Steve" <mathgroup at smc.vnet.net>; 
Peter Pein <petsie at dordos.net>
> Sent: Thursday, October 6, 2011 9:48 PM
> Subject: Re: Re: simplification
>
>
> On 6 Oct 2011, at 20:28, Andrzej Kozlowski wrote:
>
> >
> > On 6 Oct 2011, at 16:57, Andrzej Kozlowski wrote:
> >
> >>
> >> On 5 Oct 2011, at 10:01, Peter Pein wrote:
> >>
> >>> Am 04.10.2011 07:40, schrieb dimitris:
> >>>> Hello.
> >>>>
> >>>> Let
> >>>>
> >>>> o1 = 1 + Sqrt[15 + 2*Sqrt[35] + 2*Sqrt[6*(6 + Sqrt[35])]];
> >>>> o2 = 1 + Sqrt[3] + Sqrt[5] + Sqrt[7];
> >>>>
> >>>> o1 is equal to o2.
> >>>>
> >>>> o1 == o2 // FullSimplify
> >>>> True
> >>>>
> >>>> The question is how to make Mathematica to simplify o1 to o2.
> >>>>
> >>>> Thanks
> >>>> Dimitris
> >>>>
> >>>
> >>> With a lot of luck:
> >>>
> >>> In[1]:= o1 = 1 + Sqrt[15 + 2*Sqrt[35] + 2*Sqrt[6*(6 + 
Sqrt[35])]];
> >>> ext = Block[{x, poly = RootReduce[o1][[1]]},
> >>> Sqrt[Cases[Union @@ Divisors[Abs[CoefficientList[poly[x], x]]],
> >>>  1 | _?PrimeQ, 1]]]
> >>> o2 = ((Rest[#1] / First[#1]) . ext & )[
> >>>      FindIntegerNullVector[Prepend[ext, -o1]]]
> >>>
> >>> Out[3]= {1, Sqrt[2], Sqrt[3], Sqrt[5], Sqrt[7], Sqrt[19], 
Sqrt[31]}
> >>>
> >>> Out[4]= 1 + Sqrt[3] + Sqrt[5] + Sqrt[7]
> >>>
> >>> :-)
> >>>
> >>
> >> Neat, but from the Mathematical point of view the question was 
posed "the wrong way round" in that o1 is mathematically "simpler" than 
1 + Sqrt[3] + Sqrt[5] + Sqrt[7], since it is already expressed in terms 
of its minimal polynomial. Hence this is the "natural" or "easy" way to 
go:
> >>
> >> ToRadicals[RootReduce[1 + Sqrt[3] + Sqrt[5] + Sqrt[7]]]
> >>
> >> 1 + Sqrt[15 + 2*Sqrt[35] + 2*Sqrt[6*(6 + Sqrt[35])]]
> >>
> >> in other words, the algebraic "simplification" in this case is 
exactly the opposite of, what might be called, the visual one.
> >>
> >>
> >> There is no natural or unique way to "decompose" algebraic numbers 
that are already reduced into sums etc, of "simpler" summands or factors 
etc. Of course, if we already know an integer basis for an algebraic 
number field containing an algebraic number, than there are ways of 
expressing it in terms of this basis - and this method is an example.
> >>
> >> Andrzej Kozlowski
> >>
> >>
> >>
> >>
> >
> > Let me correct myself here since I noticed that I did not write what 
I really meant ;-)
> >
> > What I mean was that the following is the simplest (algebraically) 
form of this algebraic number:
> >
> > In[80]:= RootReduce[1 + Sqrt[3] + Sqrt[5] + Sqrt[7]]
> >
> > Out[80]= Root[
> > 1024 + 3584 #1 + 640 #1^2 - 1984 #1^3 - 48 #1^4 + 304 #1^5 -
> >  32 #1^6 - 8 #1^7 + #1^8 &, 8]
> >
> > (the same as above, but, of course, without the ToRadicals). 
Mathematically equivalent statement is:
> >
> > MinimalPolynomial[RootReduce[1+Sqrt[3]+Sqrt[5]+Sqrt[7]],x]
> > 1024+3584 x+640 x^2-1984 x^3-48 x^4+304 x^5-32 x^6-8 x^7+x^8
> >
> > The only simplification one can really make algorithmically with 
algebraic numbers is what RootReduce does - essentially finding the 
minimal polynomial. Mathematica also has an algorithm for converting 
some root objects to radicals but this is usually does not give the 
visually simplest form. There is no algorithm that will discover the 
simples such form in general (indeed, most algebraic numbers can't be 
expressed in radicals at all). On the other hand, one can find the 
minimal polynomial of any algebraic number: e.g.
> >
> > In[82]:= MinimalPolynomial[1 + Sqrt[3] + Sqrt[5] + Sqrt[7], x]
> > Out[82]= 1024 + 3584*x + 640*x^2 - 1984*x^3 - 48*x^4 + 304*x^5 - 
32*x^6 - 8*x^7 + x^8
> >
> > In[83]:= 
MinimalPolynomial[1+Sqrt[15+2*Sqrt[35]+2*Sqrt[6*(6+Sqrt[35])]],x]
> > Out[83]= 1024+3584 x+640 x^2-1984 x^3-48 x^4+304 x^5-32 x^6-8 
x^7+x^8
> >
> > You get the same answer which is how Mathematica knowns that these 
numbers are really equal - it does not attempt to transform one into the 
other. When I wrote that
> > 1+Sqrt[15+2*Sqrt[35]+2*Sqrt[6*(6+Sqrt[35])] was "algebraically 
simpler" than 1+Sqrt[3]+Sqrt[5]+Sqrt[7]] I meant only that the former is 
Mathematica's radical representation of Root[1024 + 3584 #1 + 640 #1^2 - 
1984 #1^3 - 48 #1^4 + 304 #1^5 - 32 #1^6 - 8 #1^7 + #1^8 &, 8] - which 
is indeed the simplest way (algebraically) to express this algebraic 
number, which, of course, has infinitely many other representations in 
terms of radicals (which Mathematica will not be able, in general, to 
convert into one another but will always be able to find their minimal 
polynomial).
> >
> > This is not a limitation of Mathematica - it is a limitation of the 
radical representation of algebraic numbers.
> >
> > Andrzej Kozlowski
> >
> >
> >
>
>
> Even the above was still not quite accurate. MinimalPolynomial of an 
algebraic number, still does not determine it - obviously
>
> MinimalPolynomial[
> Root[1024 + 3584 #1 + 640 #1^2 - 1984 #1^3 - 48 #1^4 + 304 #1^5 -
>     32 #1^6 - 8 #1^7 + #1^8 &, 8], x]
>
> 024 + 3584 x + 640 x^2 - 1984 x^3 - 48 x^4 + 304 x^5 -
> 32 x^6 - 8 x^7 + x^8
>
> MinimalPolynomial[Root[1024+3584 #1+640 #1^2-1984 #1^3-48 #1^4+304 
#1^5-32 #1^6-8 #1^7+#1^8&,7],x]
> 1024+3584 x+640 x^2-1984 x^3-48 x^4+304 x^5-32 x^6-8 x^7+x^8
>
> but of course these roots themselves are not the same. However, once 
you know the minimal polynomial of an algebraic number you only need to 
isolate it from the other roots to determine it uniquely - which is 
something that Mathematica does automatically when it numbers the roots. 
So, once you determine the minimal polynomials of two algebraic numbers 
we know that if the polynomials are different so are the numbers, if 
they are the same we use root isolation to distinguish or identify them. 
In any case, the point it that no transformations are performed on 
radicals when doing this sort of thing.
>
>
>




  • Prev by Date: Re: Formatting in XLS(X) files
  • Next by Date: Re: Constructing a huge graph
  • Previous by thread: Re: Re: simplification
  • Next by thread: Re: find two numbers a,b, such that a+b=5432 & LCM[a,b]=223020