The Math Forum

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: Composites, and neat relation
Replies: 18   Last Post: Sep 14, 2004 3:38 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]

Posts: 9,787
Registered: 12/4/04
Re: Composites, and neat relation
Posted: Sep 12, 2004 9:27 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply (James Harris) wrote in message news:<>...
> So someone pointed out that there's the trivial relation
> [x] + [x + 1/2] = [2x] where you're in reals,
> and I started thinking about
> [x] + [x + 1/k] = [2x]
> also in reals, with k>1, and it turns out you need x>1 as well, which
> I was thinking about didn't put down before.

You can have x less than 1 as what's needed is

xk + 1 >= k

where that might be useful in using what might be a probabilitic prime
test as way to factor as I'll explain below...

> Using that with x = N/2kj, where N, k and j are naturals, and N>=2kj,
> you get
> [(N+2j)/2kj] = [N/kj] - [N/2kj]

What's really neat here is that I've split kj.

> and to test it, I'll use N=13, k=2, j=3, which gives
> [19/12] = [13/6] - [13/12]
> so that works.
> That should say something about what j can be in general given a
> composite, but I'd think it'd just repeat what you can find by other
> means.
> Still I'm mulling it over and don't mind tossing it out early.
> After all, if kj is prime, then only j = 1, or j=k, will work,

Actually, only j=1 will *always* work, if kj is prime.

> assuming that j is the one that equals 1.

It has to be.

> Is there some way then, given some composite C, to play with
> [(N+2j)/2C] = [N/C] - [N/2C]
> where N>2C, to determine if j can be other than 1 or C?
> If so, then it's a prime test.

It should actually work. Basically you should be able to sample with
various N's and calculate what j will work.

The more N's you sample--possibly randomly--the closer to the actual
value of j you should get.

So, it would actually factor kj, and if kj is prime, your j would
consistently decrease as it approached 1.

Neat. I wonder how well it works.

James Harris

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.