Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: A quicker way?
Posted:
Feb 5, 2013 5:00 AM
|
|
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
|
|
|
|
