Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: A quicker way?
Replies: 1   Last Post: Feb 5, 2013 5:00 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View  
mluttgens

Posts: 73
Registered: 3/3/11
Re: A quicker way?
Posted: Feb 5, 2013 5:00 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Le lundi 4 février 2013 19:23:36 UTC+1, konyberg a écrit :
> On Monday, February 4, 2013 7:05:18 PM UTC+1, lut...@gmail.com wrote:
>

> > Le lundi 4 février 2013 18:04:31 UTC+1, quasi a écrit :
>
> >
>
> > > luttgma@gmail.com wrote:
>
> >
>
> > >
>
> >
>
> > > >quasi wrote:
>
> >
>
> > >
>
> >
>
> > > >> quasi wrote:
>
> >
>
> > >
>
> >
>
> > > >> >luttgma@gmail.com wrote:
>
> >
>
> > >
>
> >
>
> > > >> >>
>
> >
>
> > >
>
> >
>
> > > >> >>Let n^2 = N + a^2, where n, N and a are integers.
>
> >
>
> > >
>
> >
>
> > > >> >>
>
> >
>
> > >
>
> >
>
> > > >> >>Knowing N, it is of course possible to find n by trying
>
> >
>
> > >
>
> >
>
> > > >> >>
>
> >
>
> > >
>
> >
>
> > > >> >> a = 1, 2, 3, 4, etc...
>
> >
>
> > >
>
> >
>
> > > >> >>
>
> >
>
> > >
>
> >
>
> > > >> >>But doesn't exist a quicker way ?
>
> >
>
> > >
>
> >
>
> > > >> >
>
> >
>
> > >
>
> >
>
> > > >> >if you rewrite the equation in the form
>
> >
>
> > >
>
> >
>
> > > >> >
>
> >
>
> > >
>
> >
>
> > > >> > (n - a)(n + a) = N
>
> >
>
> > >
>
> >
>
> > > >> >
>
> >
>
> > >
>
> >
>
> > > >> >then for each pair of integers u,v with u*v = N, you can
>
> >
>
> > >
>
> >
>
> > > >> >
>
> >
>
> > >
>
> >
>
> > > >> >solve the equations
>
> >
>
> > >
>
> >
>
> > > >> >
>
> >
>
> > >
>
> >
>
> > > >> > n - a = u
>
> >
>
> > >
>
> >
>
> > > >> >
>
> >
>
> > >
>
> >
>
> > > >> > n + a = v
>
> >
>
> > >
>
> >
>
> > > >> >
>
> >
>
> > >
>
> >
>
> > > >> >for n and a.
>
> >
>
> > >
>
> >
>
> > > >>
>
> >
>
> > >
>
> >
>
> > > >> Also, since n - a and n + a have the same parity (both even
>
> >
>
> > >
>
> >
>
> > > >> or both odd), you only need to consider pairs of integers u,v
>
> >
>
> > >
>
> >
>
> > > >> with u*v = N for which u,v are both even or both odd.
>
> >
>
> > >
>
> >
>
> > > >
>
> >
>
> > >
>
> >
>
> > > >Thank you, but then you must find u and v, which doesn't
>
> >
>
> > >
>
> >
>
> > > >seem quicker than trying a=1,2,3, etc.
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > > Sometimes it's a lot quicker.
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > > For example, try to find all pairs (n,a) of positive
>
> >
>
> > >
>
> >
>
> > > integers such that n^2 = 2^100 + a^2.
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > > Using the method a = 1,2,3, ... how long do you think it
>
> >
>
> > >
>
> >
>
> > > will take to find even one such pair?
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > >
>
> >
>
> > > quasi
>
> >
>
> >
>
> >
>
> > I am looking for a general solution of n^2 = N + a^2, but perhaps there is none.
>
> >
>
> > Btw, how long would it take to factorize N if it were the product of two very big primes?
>
> >
>
> >
>
> >
>
> > Marcel
>
>
>
> Look at Fermat's factorization method.
>
>
>
> KON


Thank you, but I read in
http://www.trans4mind.com/personal_development/mathematics/numberTheory/divisibilityFermat.htm
that
"When the factors aren't near the root of the number, the method works very slowly, perhaps as slowly as trial division, with far more work!"

Marcel



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.