Re: SF: Infinity proof
From: David Kastrup (dak_at_gnu.org)
Date: 04/17/05
- Next message: Bruce Stephens: "Re: SF: Infinity proof"
- Previous message: José Carlos Santos: "Re: SF: Infinity proof"
- In reply to: jstevh_at_msn.com: "SF: Infinity proof"
- Next in thread: Bruce Stephens: "Re: SF: Infinity proof"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sun, 17 Apr 2005 20:12:30 +0200
jstevh@msn.com writes:
> The surrogate factoring theorem works over rationals, and from
> discussions I've seen on Usenet in response to my posts on SFT, it
> seems there's a good bit of confusion possible when it comes to
> understanding factoring in rationals.
>
> The set of rational is infinite, and because every member except 0
> is a factor of every other member, math students get taught that
> factorizations in rationals are trivial.
Uh, no. Math students actually don't get taught this, because it
really _is_ trivial, and trivial to see as well. No confusion about
that.
> But if you have
>
> a_1 a_2 = N
>
> where a_1 and a_2 are rationals, and N is a composite, and further
>
> a_1 = x/y
>
> where x and y are coprime non-zero integers, then you can check the
> gcd of x or y with N to see if you have a non-trivial factor of N.
You can check this with _any_ integer x or y.
> So the factorization, while in rationals, can still be considered
> non-trivial, if you do get a non-trivial factor from x or y.
The problem is that the "rational whatever" does not buy you anything
over considering integers in the first place. Only those
factorizations that lead to integers are interesting at all.
> So how many of the factors of N in the set of rationals are
> non-trivial?
>
> Well that's easy--an infinite number of them are.
So what are the infinite non-trivial rational factors of N=15?
> But as a percentage, how many of them are trivial?
You can't take percentages of infinities. You can only take
percentages of finite subsets, and then take them to the limit.
> Well, for every trivial factor, you can multiply it by a prime
> factor of N and get a non-trivial factor.
Which means that finding a non-trivial rational factor is as hard as
finding an integer factor. Back to square 1.
> For instance, if N is coprime to 2 and 3, then x = 2, y = 3, gives
> 2/3, a trivial factor of N. But if N has p_1 as a factor, then
> multiplying x by p_1, gives a non-trivial factor as then you have
> 2p_1/3.
>
> So for every trivial solution in that infinity you have a
> non-trivial solution found by multiplying by a single prime factor.
>
> So, as a percentage, at most 50% of the solutions are trivial for
> the composite N.
Well, according to that logic, 50% of all integers are dividable by
37, since any number not dividable by 37 can be turned into a number
dividable by 37 by multiplying by the single prime factor 37.
> Understanding that is key to understanding the importance of the
> SFT.
Truer words were seldom uttered.
-- David Kastrup, Kriemhildstr. 15, 44793 Bochum
- Next message: Bruce Stephens: "Re: SF: Infinity proof"
- Previous message: José Carlos Santos: "Re: SF: Infinity proof"
- In reply to: jstevh_at_msn.com: "SF: Infinity proof"
- Next in thread: Bruce Stephens: "Re: SF: Infinity proof"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
