- Perhaps it is K*p+1?

Harsh

--- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>

wrote:> Hi,

the

>

> Perhaps, I didn't put it the right way.

>

> Where p+1 is prime it divides n^p - 1

>

> i.e. 11 divides 2^10-1 and 23 divides 2^22-1

>

> More importantly, for my example, 89 divides 3^88-1 .

>

> However, if you have a counter-example then please send it to me.

>

> Kevin.

>

>

>

> At 02:06 PM 2/07/2004, eharsh82 wrote:

> >Taken another way p+1 divides n^p - 1.

> >

> >This isn't true.

> >

> >Harsh

> >

> >

> >--- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>

> >wrote:

> > > OK, here's a bombproof way to factorize a Mersenne, given that

> > > algorithm is implementable in a computer. Please make me aware

of

> >any

number to

> > > counter-example should you know of one.

> > >

> > > Remember that we are dealing solely with an exponent of a

> >a given

computer

> > > base. You don't need to keep the actual number itself in

> >memory

in a

> > > in an implementation.

> > >

> > > Given that the "reverse method" can find the smallest exponent

> >given

n

> > > base for a given number.

> > >

> > > And given that p divides (n^(p-1))-1 where p is prime or a base

> > > pseudoprime. Taken another way p+1 divides n^p - 1.

check it

> > >

> > > Take a number known to be composite, in this case 2047 and

> >against

and

> > > the smallest 3^n -1 number that it can divide.

> > >

> > > The reverse method shows us that 2047 divides 2^11-1 (itself)

> >3^88 - 1.

88+1

> > >

> > > We now know for sure that 2047 isn't prime because 88 doesn't

> >divide 2046,

> > > (2047-1).

> > >

> > > We also know that x+1 will divide 3^x -1. In this case x+1 is

> >or 89.

base

> > >

> > > Now we find that 89 divides 2047 giving us 23, the other factor.

> > > Effectively factorizing 2^11-1 without ever having to work in

> >2.

divides

> > >

> > > Now take another number, this time known to be prime, 8191

> > >

> > > Applying the reverse algorithm in base 3 we find that 8191

> >3^8190 -

The

> > > 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3.

> >reverse

cases

> > > algorithm in base 2 shows that 8191 divides 2^13-1 and that 13

> >divides

> > > 8190, therefore 8191 is base 2 prime as well.

> > >

> > > So am I wrong or does this method of factorizing work in all

> >for

unsubscribe@yahoogroups.com

> > > Mersenne numbers?

> > >

> > > Kevin.

> >

> >

> >

> >

> >Unsubscribe by an email to: primenumbers-

> >The Prime Pages : http://www.primepages.org/

> >

> >

> >Yahoo! Groups Links

> >

> >

> >

> > - Yes it should work!

"Take a number known to be composite, in this case 2047 and check it

against the smallest 3^n -1 number that it can divide."

Finding n is really difficult for large numbers. So your algorithm is

not practical.

Harsh

--- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>

wrote:> OK, here's a bombproof way to factorize a Mersenne, given that the

any

> algorithm is implementable in a computer. Please make me aware of

> counter-example should you know of one.

a given

>

> Remember that we are dealing solely with an exponent of a number to

> base. You don't need to keep the actual number itself in computer

memory

> in an implementation.

given

>

> Given that the "reverse method" can find the smallest exponent in a

> base for a given number.

against

>

> And given that p divides (n^(p-1))-1 where p is prime or a base n

> pseudoprime. Taken another way p+1 divides n^p - 1.

>

> Take a number known to be composite, in this case 2047 and check it

> the smallest 3^n -1 number that it can divide.

3^88 - 1.

>

> The reverse method shows us that 2047 divides 2^11-1 (itself) and

>

divide 2046,

> We now know for sure that 2047 isn't prime because 88 doesn't

> (2047-1).

or 89.

>

> We also know that x+1 will divide 3^x -1. In this case x+1 is 88+1

>

2.

> Now we find that 89 divides 2047 giving us 23, the other factor.

> Effectively factorizing 2^11-1 without ever having to work in base

>

3^8190 -

> Now take another number, this time known to be prime, 8191

>

> Applying the reverse algorithm in base 3 we find that 8191 divides

> 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3. The

reverse

> algorithm in base 2 shows that 8191 divides 2^13-1 and that 13

divides

> 8190, therefore 8191 is base 2 prime as well.

for

>

> So am I wrong or does this method of factorizing work in all cases

> Mersenne numbers?

>

> Kevin. - Actually it is practical.

Remember that you don't store the actual number, only the exponent. So in

the example of 3^88-1 I know that everything below my addition point is

2222222..... As such it gets discarded. I only count how many 2's I get in

the string.

Kevin.

At 04:26 PM 2/07/2004, eharsh82 wrote:>Yes it should work!

>

>"Take a number known to be composite, in this case 2047 and check it

>against the smallest 3^n -1 number that it can divide."

>

>Finding n is really difficult for large numbers. So your algorithm is

>not practical.

>

>

>Harsh

>

>

>

>

>

>--- In primenumbers@yahoogroups.com, Kevin Acres <research@r...>

>wrote:

> > OK, here's a bombproof way to factorize a Mersenne, given that the

> > algorithm is implementable in a computer. Please make me aware of

>any

> > counter-example should you know of one.

> >

> > Remember that we are dealing solely with an exponent of a number to

>a given

> > base. You don't need to keep the actual number itself in computer

>memory

> > in an implementation.

> >

> > Given that the "reverse method" can find the smallest exponent in a

>given

> > base for a given number.

> >

> > And given that p divides (n^(p-1))-1 where p is prime or a base n

> > pseudoprime. Taken another way p+1 divides n^p - 1.

> >

> > Take a number known to be composite, in this case 2047 and check it

>against

> > the smallest 3^n -1 number that it can divide.

> >

> > The reverse method shows us that 2047 divides 2^11-1 (itself) and

>3^88 - 1.

> >

> > We now know for sure that 2047 isn't prime because 88 doesn't

>divide 2046,

> > (2047-1).

> >

> > We also know that x+1 will divide 3^x -1. In this case x+1 is 88+1

>or 89.

> >

> > Now we find that 89 divides 2047 giving us 23, the other factor.

> > Effectively factorizing 2^11-1 without ever having to work in base

>2.

> >

> > Now take another number, this time known to be prime, 8191

> >

> > Applying the reverse algorithm in base 3 we find that 8191 divides

>3^8190 -

> > 1. 8190 divides 8191-1 so we now that 8191 is prime in base 3. The

>reverse

> > algorithm in base 2 shows that 8191 divides 2^13-1 and that 13

>divides

> > 8190, therefore 8191 is base 2 prime as well.

> >

> > So am I wrong or does this method of factorizing work in all cases

>for

> > Mersenne numbers?

> >

> > Kevin.

>

>

>

>

>Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

>The Prime Pages : http://www.primepages.org/

>

>

>Yahoo! Groups Links

>

>

>

>