Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Square free numbers
Replies:
25
Last Post:
May 13, 2002 4:04 PM




Re: Square free numbers
Posted:
May 8, 2002 6:05 PM


Nicol So <nobody@no.spam.please> wrote in message news:<3CD94FC5.4826E3A2@no.spam.please>... > Phil Carmody wrote: > > > > nospam wrote: > > > > > > How do I determine if a number is square free, > > > without knowing its factors? > > > > The problem is as hard as factoring. > > How do you do factoring given the ability to decide squarefreeness?
Good question! :o)
To rephrase Phil's statement, the fastest method *known* for testing squarefreeness requires factoring (AFAIK). See page 8 of the paper "The factorization of the 9th Fermat number" for more details. You can download it from Mark Manesse's web page:
http://www.research.compaq.com/SRC/personal/msm/common/f9paper.ps
Scott



