wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Fermat numbers
        
(Message started by: BenVitale on Feb 18^th, 2008, 2:26pm)

Title: Fermat numbers
Post by BenVitale on Feb 18^th, 2008, 2:26pm

Could anyone please provide a link to a method of factorization of Fermat numbers (using the Pollard rho method) ?

Title: Re: Fermat numbers
Post by Grimbal on Feb 19^th, 2008, 1:24am

Have you tried searching for "pollard rho" in MathWorld, Wikipedia or Google?

Title: Re: Fermat numbers
Post by towr on Feb 19^th, 2008, 1:39am

http://mathworld.wolfram.com/PollardRhoFactorizationMethod.html
http://en.wikipedia.org/wiki/Pollard_rho
http://www.google.com/search?q=pollard+rho

Title: Re: Fermat numbers
Post by BenVitale on Feb 19^th, 2008, 11:48am

Yes, I've tried. Sorry, my question was somewhat vague.

The Pollard rho factorization method is a method for factorizing integers into their prime number components. I'm trying to understand why this method works especially well for factorizing numbers whose prime factors fall into a particular congruence class, and thus making it an ideal method for factorizing Fermat numbers.
Why?

And, how can we use The Pollard rho factorization method to solve the "Birthday problem"?

This is what I have in mind.

Title: Re: Fermat numbers
Post by BenVitale on May 13^th, 2008, 2:51pm

Counterexample to Fermat's Last Theorem
70^3 = 3 4 3 0 0 0
212^3 = 9 5 2 8 1 2 8
----------------------------------
462^3 = 9 8 6 11 1 2 8

found by Erich Friedman.

http://mathpuzzle.com/

Title: Re: Fermat numbers
Post by towr on May 13^th, 2008, 11:54pm

How is that a counterexample?

9871128 isn't equal to 98611128

Considering Fermat's last theorem was proven to be true, it would be very surprising to find an actual counter-example, as it would mean mathematics is inconsistent.

Title: Re: Fermat numbers
Post by BenVitale on May 14^th, 2008, 12:42am

on 05/13/08 at 23:54:23, towr wrote:

Yes, I know. That's the reason I posted the link. I don't understand what's going on here.

mathpuzzle.com has a good reputation, though.

Any thoughts?

Title: Re: Fermat numbers
Post by pex on May 14^th, 2008, 12:55am

on 05/14/08 at 00:42:54, BenVitale wrote:

Yes, I know. That's the reason I posted the link. I don't understand what's going on here.

mathpuzzle.com has a good reputation, though.

Any thoughts?

Errr... How about carrying the 1 when an intermediate result in adding is 11?

Title: Re: Fermat numbers
Post by ThudanBlunder on May 14^th, 2008, 3:09am

on 05/14/08 at 00:42:54, BenVitale wrote:

Yes, I know. That's the reason I posted the link. I don't understand what's going on here.

Any thoughts?

It's obviously a joke, a 'near miss'.

Title: Re: Fermat numbers
Post by Christine on Jul 18^th, 2008, 11:18pm

Suppose you have a set of triangles ABC so that a^n+b^n=c^n without restricting that a,b and c all had to be rational length. Suppose side c coincides with the x axis with the midpoint at the origin. Let c=2. If y is perpendicular to x meeting at the vertex C where sides a and b meet, then I figured by the pythatgorean theorem that a^2=(1+x)^2+y^2 and b^2=(1-x)^2+ y^2. Since I'm proposing that a^n+b^n=2^n, then it follows that [(1+x)^2+y^2] ^(n/2)+[( 1-x)^2+y^ 2]^(n/2)= 2^n. If you let n=2 and simplify, then the result is the equation for the unit circle, which fits because a^2+b^2=c^2, where c=2 in this case. This formula generates a set of curves for each n so that a point (x,y) on this curve is the vertex of all triangles that satisfy the propostion. if FLT is true, then x and y can't both be rational because if they were, then a and b could be both rational. I can't prove this though, or even if my logic is correct. If I express it as a parametric equation, but I don't know how. By supposing that r is the radius from the origin to (x,y) and that r^2=x^2+y^2 and using the law of cosines for a and b with common side r and third side=1, would that be any help?

Title: Re: Fermat numbers
Post by Eigenray on Jul 19^th, 2008, 1:22am

This doesn't have anything to do with Fermat numbers. Also, I'm not sure what you are asking. Do you want to know whether
[ (1+x)² + y² ]^n/2 + [ (1-x)² + y² ]^n/2 = 2ⁿ
has any rational solutions?

If n>4 is even, then it follows from FLT that there are no non-trivial rational solutions. In fact FLT has been proven for rational exponents as well, so if n>1 is odd there are also no non-trivial solutions. The trivial solutions are (x,y)=(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1, 0).

For n=1 we have a+b=c so there are only the degenerate triangles with y=0.

For n=2 we have a circle in which the rational points are dense.

The case n=4 is a bit tricky. We can solve
y² = -1-x² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{2-x²}.
If x,y are rational then 2-x² = z² for some rational z. Note that (x,z)=(1,1) is a rational point on this curve. If (x,z) is any other point, then (z-1)/(x-1)=m is rational, and we can use these two equations to solve for (x,z) in terms of m. This gives
x = (m²-2m-1)/(m²+1)
z = (1-2m-m²)/(m²+1)
as a complete parameterization. But now we need
y² = -1-x² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif2z
= 4(m-1)(2m²+m+1)/(m²+1)² or
-4m(1+m)(2-m+m²)/(1+m²)².
In fact replacing m with -1/m turns the second expression into the first, so let's stick to that. For this to be a square, we must have (m-1)(2m²+m+1) a square. This is the equation of an elliptic curve, and it can be shown that the only rational point on it has m=1, giving the point (x,y)=(-1,0), or (1,0) if we replace m by -1/m.

Title: Re: Fermat numbers
Post by Eigenray on Jul 19^th, 2008, 1:58am

Here is the proof of FLT for rational exponents, as found in:

Curtis D Bennett, A M W Glass, Gabor J Szekely. (2004). Fermat's Last Theorem for Rational Exponents. The American Mathematical Monthly, 111(4), 322-329.

Theorem: There are no solutions to x^n/m + y^n/m = 1, x,y>0 rational, n,m relatively prime, n>2. (See below if roots need not be real.)

Lemma: Suppose http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif>0 and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif^m is rational. Then the minimal polynomial of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif is f(x) = x^k - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif^k, where k is the smallest positive integer such that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif^k is rational.

Proof: Let p(x) be the minimal polynomial of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif, say of degree d. Then p|f, and the constant term p₀ of p is a rational number which is a product of d of the roots of f, which are each of the form http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gifⁱhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif, where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif is a k-th root of unity. Thus p₀ = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif^d; since this is rational, d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif k. The result follows.

Proof of Theorem: Let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif= x^n/m. By the Lemma, the minimal polynomial of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif is f(x) = x^d - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif^d, where d is the degree of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif over the rationals. The same argument applies to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif= y^n/m, and because http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif=1, they have the same degree. So g(x) = x^d - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif^d is the minimal polynomial of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif.

Now g(1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif)=g(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif)=0, i.e., http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif is a root of (1-x)^d - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif^d. But since http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif has degree d, this must be (up to a constant) the minimal polynomial of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif. That is,
x^d - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif^d = (-1)^d [ (1-x)^d - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif^d ].
The only way this can happen is if d=1, meaning http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/beta.gif are both rational.

Now because n,m are relatively prime, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif=x^n/m is rational, x must already be an m-th power, and similarly for y; say x=r^m, y=s^m. But now we have
rⁿ + sⁿ = 1,
so if n>2, the regular version of FLT implies there are no solutions with r,s>0.

This is assuming that all roots are real. If we allow complex roots, all non-trivial solutions look like

x^n/(6m) + x^n/(6m) = x^n/(6m),

where we take 3 different 6-th roots; e.g., http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif+ http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif^-1 = 1, where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/zeta.gif= e^{pi i/6}.

Title: Re: Fermat numbers
Post by Christine on Jul 21^st, 2008, 10:41pm

on 07/19/08 at 01:22:41, Eigenray wrote:

Oops, you're right, sorry, this has nothing to do with Fermat numbers. I was heavily into golden ratio like formulas and somehow changed in a fascination with Fermat's Last Theorem.

And, thanks for the solution.

This (implicit?) function gives a set of curves for each n so that if lines are drawn from a point on this curve to the ends of the minor axis which equals 2, call these sides a and b, then a^n+b^n=2^n in terms of the (x,y) coordinates where a and b are real numbers.

Before F.L.T. proof came out, I thought that the (x,y) coordinates are never both rational for n>2 because if they were, then a and b could both be rational which would disprove F.L.T. I want to show that this is the case, but I don't know if my logic is flawed or what. In the case where n=2, the result is the function for a unit circle. By the Pythagorean theorem, a^2+b^2=4 has both rational (x,y) for rational a and b. Are the curves for n>2 non modular elliptic curves?