Author |
Topic: Fermat numbers (Read 1680 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
Fermat numbers
« on: Feb 18th, 2008, 2:26pm » |
 Quote  Modify
|
Could anyone please provide a link to a method of factorization of Fermat numbers (using the Pollard rho method) ?
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Fermat numbers
« Reply #1 on: Feb 19th, 2008, 1:24am » |
Quote Modify
|
Have you tried searching for "pollard rho" in MathWorld, Wikipedia or Google?
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Fermat numbers
« Reply #3 on: Feb 19th, 2008, 11:48am » |
Quote Modify
|
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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Fermat numbers
« Reply #4 on: May 13th, 2008, 2:51pm » |
Quote Modify
|
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/
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Fermat numbers
« Reply #5 on: May 13th, 2008, 11:54pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Fermat numbers
« Reply #6 on: May 14th, 2008, 12:42am » |
Quote Modify
|
on May 13th, 2008, 11:54pm, towr wrote: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. |
|
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?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Fermat numbers
« Reply #7 on: May 14th, 2008, 12:55am » |
Quote Modify
|
on May 14th, 2008, 12:42am, 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?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Fermat numbers
« Reply #8 on: May 14th, 2008, 3:09am » |
Quote Modify
|
on May 14th, 2008, 12:42am, 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'.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: Fermat numbers
« Reply #9 on: Jul 18th, 2008, 11:18pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Fermat numbers
« Reply #10 on: Jul 19th, 2008, 1:22am » |
Quote Modify
|
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)2 + y2 ]n/2 + [ (1-x)2 + y2 ]n/2 = 2n
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)=( 1, 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
y2 = -1-x2 2 {2-x2}.
If x,y are rational then 2-x2 = z2 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 = (m2-2m-1)/(m2+1)
z = (1-2m-m2)/(m2+1)
as a complete parameterization. But now we need
y2 = -1-x2 2z
= 4(m-1)(2m2+m+1)/(m2+1)2 or
-4m(1+m)(2-m+m2)/(1+m2)2.
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)(2m2+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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Fermat numbers
« Reply #11 on: Jul 19th, 2008, 1:58am » |
Quote Modify
|
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 xn/m + yn/m = 1, x,y>0 rational, n,m relatively prime, n>2. (See below if roots need not be real.)
Lemma: Suppose  >0 and m is rational. Then the minimal polynomial of is f(x) = xk - k, where k is the smallest positive integer such that k is rational.
Proof: Let p(x) be the minimal polynomial of , say of degree d. Then p|f, and the constant term p0 of p is a rational number which is a product of d of the roots of f, which are each of the form  i, where is a k-th root of unity. Thus p0 = d; since this is rational, d  k. The result follows.
Proof of Theorem: Let = xn/m. By the Lemma, the minimal polynomial of is f(x) = xd - d, where d is the degree of over the rationals. The same argument applies to  = yn/m, and because +=1, they have the same degree. So g(x) = xd - d is the minimal polynomial of .
Now g(1-)=g()=0, i.e., is a root of (1-x)d - d. But since has degree d, this must be (up to a constant) the minimal polynomial of . That is,
xd - d = (-1)d [ (1-x)d - d ].
The only way this can happen is if d=1, meaning and are both rational.
Now because n,m are relatively prime, and =xn/m is rational, x must already be an m-th power, and similarly for y; say x=rm, y=sm. But now we have
rn + sn = 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
xn/(6m) + xn/(6m) = xn/(6m),
where we take 3 different 6-th roots; e.g., + -1 = 1, where = epi i/6.
|
| « Last Edit: Jul 19th, 2008, 2:05am by Eigenray » |
IP Logged |
|
|
|
Christine
Full Member
Posts: 159
|
|
Re: Fermat numbers
« Reply #12 on: Jul 21st, 2008, 10:41pm » |
Quote Modify
|
on Jul 19th, 2008, 1:22am, Eigenray wrote: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)2 + y2 ]n/2 + [ (1-x)2 + y2 ]n/2 = 2n
has any rational solutions?
....... |
|
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?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print