--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> Exercise: Find the algebraic factors of 16^137-1.
>

Same game with 61^73-60^73, 140^71-139^71 and 138^127-137^127.

JL

--- In primenumbers@yahoogroups.com,
"j_chrtn" <j_chrtn@...> wrote:

> "djbroadhurst" <d.broadhurst@> wrote:
> > Exercise: Find the algebraic factors of 16^137-1.
>
> Same game with 61^73-60^73, 140^71-139^71 and 138^127-137^127.

That looks to me like a very different ball game.
How might Léon-François-Antoine help us to find
/algebraic/ factors in the cases given by Jean-Louis?

Hints for the exercise:
The 6 non-unit /algebraic/ factors of
16^137-1 = f1*f2*f3*f4*f5*f6
may be found in one's head; no need for a computer.
The largest, f6, has 42 digits, yet may be written in 7 characters.
The next-to-largest, f5, may be written in 12 characters.

David

--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
> >
> > Same game with 61^73-60^73, 140^71-139^71 and 138^127-137^127.
>
> That looks to me like a very different ball game.
> How might Léon-François-Antoine help us to find
> /algebraic/ factors in the cases given by Jean-Louis?
>

Hi David,

Kermit speek about getting factors of differences of 2 powers.
The 3 "games" above are differences of 2 powers. Aren't they?
However, I must admit I was kidding (Kermit precised "where one power is
significantly larger that the other")...

Actually, this is more a job for Pollard-Williams-Lenstra that for
Léon-François-Antoine Aurifeuille.

I must also admit that I'm still stuck on the third game.
;-)

JL

--- In primenumbers@yahoogroups.com,
"j_chrtn" <j_chrtn@...> wrote:

> Kermit speek about getting factors of differences of 2 powers.

Correction: Kermit spoke about

> getting the algebraic factors of the difference of two powers

Jean-Louis wilfully omitted the important adjective :-)

David

djbroadhurst wrote:
> --- In primenumbers@yahoogroups.com,
> "j_chrtn" <j_chrtn@...> wrote:
>
>> "djbroadhurst" <d.broadhurst@> wrote:
>>> Exercise: Find the algebraic factors of 16^137-1.
>>
>> Same game with 61^73-60^73, 140^71-139^71 and 138^127-137^127.
>
> That looks to me like a very different ball game.
> How might Léon-François-Antoine help us to find
> /algebraic/ factors in the cases given by Jean-Louis?
>
> Hints for the exercise:
> The 6 non-unit /algebraic/ factors of
> 16^137-1 = f1*f2*f3*f4*f5*f6
> may be found in one's head; no need for a computer.
> The largest, f6, has 42 digits, yet may be written in 7 characters.
> The next-to-largest, f5, may be written in 12 characters.
>

Surely the largest algebraic factor of 16^137-1 is 4^137+1 which has 83
digits?

There are twelve prime factors of 16^137-1 (=2^548-1), which are
3 5 1097 15619 189061 168434085820849 32127963626435681
105498212027592977 32032215596496435569 5439042183600204290159
206875670104957744917147613 921525707911840587390617330886362701

> David

--
Jane

David:
> > Hints for the exercise:
> > The 6 non-unit /algebraic/ factors of
> > 16^137-1 = f1*f2*f3*f4*f5*f6
> > may be found in one's head; no need for a computer.

Jane
> There are twelve prime factors of 16^137-1 (=2^548-1), which are
> 3 5 1097 15619 189061 168434085820849 32127963626435681
> 105498212027592977 32032215596496435569 5439042183600204290159
> 206875670104957744917147613 921525707911840587390617330886362701

Looks like you missed the point (purposely?).  You are to find the
algebraic factors by hand, from there one could seek prime factors.
This is great problem from David as it uses some fun identities.

CC

--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> Jean-Louis wilfully omitted the important adjective :-)
>

The important adjective which was furthermore in Kermit's thread subject.
;-)

J-L

--- In primenumbers@yahoogroups.com,
"Jane Sullivan" <janesullivan@...> wrote:

> Surely the largest algebraic factor of 16^137-1 is
> 4^137+1 which has 83 digits

Not so, Jane. According to Léon-François-Antoine
the largest algebraic factor has 42 digits.
Try googling him; he is rather useful in this case :-)

Best regards

David

--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> > Surely the largest algebraic factor of 16^137-1 is
> > 4^137+1 which has 83 digits
>
> Not so, Jane. According to Léon-François-Antoine
> the largest algebraic factor has 42 digits.
> Try googling him; he is rather useful in this case :-)

Here is a really big hint; try googling:

"Léon-François-Antoine" -Fleury

/exactly/ as written above.

David

djbroadhurst wrote:
> --- In primenumbers@yahoogroups.com,
> "djbroadhurst" <d.broadhurst@...> wrote:
>
>>> Surely the largest algebraic factor of 16^137-1 is
>>> 4^137+1 which has 83 digits
>>
>> Not so, Jane. According to Léon-François-Antoine
>> the largest algebraic factor has 42 digits.
>> Try googling him; he is rather useful in this case :-)

In that case, I'm afraid Léon-François-Antoine is wrong.
(4^137+1)(4^137-1) = 4^274-1 = 4^(2x137)-1 = (4^2)^137-1 = 16^137-1.
If you say that is not an algebraic factorization, then I'm sorry,
you're wrong. It is a simple difference of two squares factorization
(a^2-b^2) = (a+b)(a-b).

We may be talking at cross purposes here: I think you are looking at
Aurifeuillian factorizations, but there are algebraic factors that are
not Aurifeuillian.

>
> Here is a really big hint; try googling:
>
> "Léon-François-Antoine" -Fleury
>
> /exactly/ as written above.

Yes I googled that, but I can't find anything relating to 137. Maybe I
gave up too easily.

>
> David

Best wishes
--
Jane

16^137-1 == 16*u^8-1, if we choose u == 16^17 == 2^68.

16*u^8-1 == (2*u^2-2*u+1)(2*u^2-1)(2*u^2+1)(2*u^2+2*u+1).

Substitute back u == 2^68, we get:

     (2^137-2^69+1)(2^137-1)(2^137+1)(2^137+2^69+1)

The two middle terms factor algebraically and we end up with
the complete algebraic factorization of 16^137-1 into 6 factors,
one of which is unfortunately the trivial unit factor (1), so
of no use for numerical factorization:

     (2^137-2^69+1)
     (2-1)
     (2^136+2^135+2^134+...+2+1)
     (2+1)
     (2^136-2^135+2^134-...-2+1)
     (2^137+2^69+1)


On 2/1/2011 10:10 AM, Jane Sullivan wrote:
> djbroadhurst wrote:
>> --- In primenumbers@yahoogroups.com,
>> "djbroadhurst"<d.broadhurst@...>  wrote:
>>
>>>> Surely the largest algebraic factor of 16^137-1 is
>>>> 4^137+1 which has 83 digits
>>>
>>> Not so, Jane. According to Léon-François-Antoine
>>> the largest algebraic factor has 42 digits.
>>> Try googling him; he is rather useful in this case :-)
>
> In that case, I'm afraid Léon-François-Antoine is wrong.
> (4^137+1)(4^137-1) = 4^274-1 = 4^(2x137)-1 = (4^2)^137-1 = 16^137-1.
> If you say that is not an algebraic factorization, then I'm sorry,
> you're wrong. It is a simple difference of two squares factorization
> (a^2-b^2) = (a+b)(a-b).
>
> We may be talking at cross purposes here: I think you are looking at
> Aurifeuillian factorizations, but there are algebraic factors that are
> not Aurifeuillian.
>
>>
>> Here is a really big hint; try googling:
>>
>> "Léon-François-Antoine" -Fleury
>>
>> /exactly/ as written above.
>
> Yes I googled that, but I can't find anything relating to 137. Maybe I
> gave up too easily.
>
>>
>> David
>
> Best wishes

--- In primenumbers@yahoogroups.com,
Jack Brennen <jfb@...> wrote:

>     (2^137-2^69+1)
>     (2-1)
>     (2^136+2^135+2^134+...+2+1)
>     (2+1)
>     (2^136-2^135+2^134-...-2+1)
>     (2^137+2^69+1)

Err, Jack, I think you missed the algebraic factor 2^2+1 ?

> Hints for the exercise:
> The 6 non-unit /algebraic/ factors of
> 16^137-1 = f1*f2*f3*f4*f5*f6
> may be found in one's head; no need for a computer.

Solution:
f1 = 2^2-1
f2 = 2^2+1
f3 = (2^137+2^69+1)/(2^2+1)
f4 = (2^137+1)/(2+1)
f5 = 2^137-2^69+1
f6 = 2^137-1

The algebra that Jane missed is
4^(2*k-1) + 1 = (2^(2*k-1) - 2^k + 1)*(2^(2*k-1) + 2^k + 1)
and if that ain't algebra, I don't know what is :-)

David

David Broadhurst wrote:

  > Exercise: Find the algebraic factors of 16137-1.

  > Comment: The maximum number of digits in any such
  > factor is 42, so if your routine produces a larger
  > factor it does not know enough algebra.

  > David

Thanks David.

I don't know enough algebra.  I would like to program the missing algebra.

After Difference of powers factoring routine, factor list is
[3, 5L,
60708402882054033466233184588234965832575213720379360039119137804340758912662765\
57L,
10118067147009005577705530764705827638762535620063226673186522967390126485443794\
261L]

Any hints will be much appreciated.

Kermit

16**137 - 1
= 2**(4*137) - 1
= (2**(2*137) - 1) (2**(2*137)   +1 )
= (2**137 - 1) (2**137 + 1) (2**(2 + 2 * 136) + 1)
= (2**137 - 1) (2 * 137 + 1) ( 4 * 2** 136 + 1)
= (2**137 - 1) (2 * 137 + 1) (4 * 16**34 + 1)

= (2**137 - 1) (2 * 137 + 1)
( 2 * 2**68 - 2 * 2**34 + 1) (2 * 2**68 + 2  * 2**34 + 1)


I had thought that I had programmed already the factoring of

(4 * 16**34 + 1)
= ( 2 * 2**68 - 2 * 2**34 + 1) (2 * 2**68 + 2  * 2**34 + 1)

But apparently there is a bug in my code for the case
that the larger fourth power is even.

But even this does not get the largest factor < 10**42.

What else do I need to know?

Kermit

>>> AlgebraicFactor(16**137-1)

After Difference of powers factoring routine, factor list is
[15, 58074857287840164431082599668355108088491L,
174224571863520493293247799005065324265471L,
60708402882054033466233184588234965832575213720379360039119137804340758912662765\
57L]

--- In primenumbers@yahoogroups.com,
Kermit Rose <kermit@...> wrote:

> I would like to program the missing algebra.

There are two types of algebraic factorization for x^n-1:
1) cyclotomic algebraic factorization
2) Aurifeuillian algebraic factorization

For (1), we use the cyclotomic polynomials,
which are obtained by Moebius transformation

  Phi(n,x)=local(P=1);fordiv(n,d,P*=(x^d-1)^moebius(n/d));P;

For (2), we must have x = m*s^2 where m is odd divisor of n.
Then for odd k, we may factorize
Phi(m*k,m*s^2), if m = 1 mod 4, and
Phi(2*m*k,m*s^2), if m = 3 mod 4.

Explicit formulas for these cases may be obtained from consulting
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0812&L=NMBRTHRY&P=446
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0812&L=NMBRTHRY&P=218
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0812&L=NMBRTHRY&P=567
with some code from Phil in the third link.

If you don't mind the time that you spend on computer algebra,
simply use GP's "factor", with /algebraic/ s.

  F=factor(Phi(17*3,17*s^2))[,1];print(vector(#F,k,poldegree(F[k])));

[32, 32]

  F=factor(Phi(2*15*3,15*s^2))[,1];print(vector(#F,k,poldegree(F[k])));

[24, 24]

with polynomial factors that are too ornate to print here.

David

Hi David,
--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
>
>
> --- In primenumbers@yahoogroups.com,
> Jack Brennen <jfb@> wrote:
>
> >     (2^137-2^69+1)
> >     (2-1)
> >     (2^136+2^135+2^134+...+2+1)
> >     (2+1)
> >     (2^136-2^135+2^134-...-2+1)
> >     (2^137+2^69+1)
>
> Err, Jack, I think you missed the algebraic factor 2^2+1 ?
>
> > Hints for the exercise:
> > The 6 non-unit /algebraic/ factors of
> > 16^137-1 = f1*f2*f3*f4*f5*f6
> > may be found in one's head; no need for a computer.
>
> Solution:
> f1 = 2^2-1
> f2 = 2^2+1
> f3 = (2^137+2^69+1)/(2^2+1)
> f4 = (2^137+1)/(2+1)
> f5 = 2^137-2^69+1
> f6 = 2^137-1
>
> The algebra that Jane missed is
> 4^(2*k-1) + 1 = (2^(2*k-1) - 2^k + 1)*(2^(2*k-1) + 2^k + 1)
> and if that ain't algebra, I don't know what is :-)
I got this bit and managed to get the 4 algebraic factors.
f3*f2 = 2^137+2^69+1
f4*f1 = 2^137+1
f5 = 2^137-2^69+1
f6 = 2^137-1
My question is how does one know algebraically (or at least without trial
dividing) that 2^2+1 divides 2^137+2^69+1 and 2^2-1 divides 2^137+1?
cheers
Ken

> David
>

--- On Fri, 1/21/11, Brian <btball@...> wrote:
> Timings on a XEON x5570 2.93 Ghz, 32GB ram:
> First place = SPSP to multiple bases. The clear winner at 4481.6 seconds
> Second place = Frobenius test at 20,070 seconds
> Third place = BPSW at 22,506 seconds

Then you're doing something wrong, or your library is optimised for one
primitive (modular exponentiation), and horrifically slow for another (lucas
sequence evaluation). What precisely was your input set?

Are you comparing up-to-12th roots of unity in the multiple SPSP test? You ought
to, that will make it a little quicker. (After the 2nd passed test there's a
>50% chance that you'll have incompatible square roots of unity, and won't need
to do a third test.)

Phil

On Tue, 2011-02-01 at 21:44 +0000, djbroadhurst wrote:
>
> --- In primenumbers@yahoogroups.com,
> Jack Brennen <jfb@...> wrote:
>
> >     (2^137-2^69+1)
> >     (2-1)
> >     (2^136+2^135+2^134+...+2+1)
> >     (2+1)
> >     (2^136-2^135+2^134-...-2+1)
> >     (2^137+2^69+1)
>
> Err, Jack, I think you missed the algebraic factor 2^2+1 ?
>
> > Hints for the exercise:
> > The 6 non-unit /algebraic/ factors of
> > 16^137-1 = f1*f2*f3*f4*f5*f6
> > may be found in one's head; no need for a computer.
>
> Solution:
> f1 = 2^2-1
> f2 = 2^2+1
> f3 = (2^137+2^69+1)/(2^2+1)
> f4 = (2^137+1)/(2+1)
> f5 = 2^137-2^69+1
> f6 = 2^137-12,548
>
> The algebra that Jane missed is
> 4^(2*k-1) + 1 = (2^(2*k-1) - 2^k + 1)*(2^(2*k-1) + 2^k + 1)
> and if that ain't algebra, I don't know what is :-)

I think you're using different vocabularies.  In the Cunningham project,
and 16^137-1 == 2,548- in their nomenclature, algebraic factors are
distinguished from Aurifeuillian factors.

Paul

--- In primenumbers@yahoogroups.com,
Paul Leyland <paul@...> wrote:

> I think you're using different vocabularies.
> In the Cunningham project, and 16^137-1 == 2,548-
> in their nomenclature, algebraic factors are
> distinguished from Aurifeuillian factors.

The problem was that Jane saw Aurifeullian and algebraic
as being mutually exclusive adjectives. They are not.

The Cunningham project uses this vocabulary:

http://www.ams.org/publications/online-books/conm22-conm22-chVII.pdf
> L,M Aurifeuillian algebraic factorization (see III C)

precisely as I did here:

http://tech.groups.yahoo.com/group/primenumbers/message/22518
> There are two types of algebraic factorization for x^n-1:
> 1) cyclotomic algebraic factorization
> 2) Aurifeuillian algebraic factorization

So at least John Brillhart, D. H. Lehmer, J. L. Selfridge,
Bryant Tuckerman, and S. S. Wagstaff, Jr agree with me,
even if Jane or Paul may not :-)

David

djbroadhurst wrote:
> --- In primenumbers@yahoogroups.com,
> Paul Leyland <paul@...> wrote:
>
>> I think you're using different vocabularies.
>> In the Cunningham project, and 16^137-1 == 2,548-
>> in their nomenclature, algebraic factors are
>> distinguished from Aurifeuillian factors.
>
> The problem was that Jane saw Aurifeullian and algebraic
> as being mutually exclusive adjectives. They are not.

No I didn't, although it might look that way.

What I was doing was objecting to the following, posted earlier in the
thread
<quote>
> Exercise: Find the algebraic factors of 16^137-1.

> Comment: The maximum number of digits in any such
> factor is 42, so if your routine produces a larger
> factor it does not know enough algebra.
</quote>

because, as I showed, there is an alegbraic (composite) factor of
16^137-1 that has 83 (i.e. more than 42) digits.

>
> The Cunningham project uses this vocabulary:
>
> http://www.ams.org/publications/online-books/conm22-conm22-chVII.pdf
>> L,M Aurifeuillian algebraic factorization (see III C)
>
> precisely as I did here:
>
> http://tech.groups.yahoo.com/group/primenumbers/message/22518
>> There are two types of algebraic factorization for x^n-1:
>> 1) cyclotomic algebraic factorization
>> 2) Aurifeuillian algebraic factorization
>
> So at least John Brillhart, D. H. Lehmer, J. L. Selfridge,
> Bryant Tuckerman, and S. S. Wagstaff, Jr agree with me,
> even if Jane or Paul may not :-)

Let me make it quite clear: I agree with you, but the statement that the
maximum number of digits in any algebraic factor of 16^137-1 is 42 is
wrong, because it's 83.

>
> David

Best wishes
--
Jane

--- In primenumbers@yahoogroups.com,
"kraDen" <kradenken@...> wrote:

> My question is how does one know algebraically
> (or at least without trial dividing) that
> 2^2+1 divides 2^137+2^69+1

We want to show that y = 2^2 + 1 divides N = 2^137 + 2^69 + 1.
Let u = 2^68. Then
N - y = 2*u^2 + 2*u - 2^2 = 2*(u-1)*(u+2).
But y divides u - 1  = (y-1)^34 - 1. Hence y divides N - y.
Hence y divides N and we are done.

Note that we do not need to compute the value of 2^2+1.
I believe that I can do that in my head, but fortunately
it is not necessary for this algebraic exercise :-)

David

--- In primenumbers@yahoogroups.com,
"Jane Sullivan" <janesullivan@...> wrote:

> there is an algebraic (composite) factor of
> 16^137-1 that has 83 (i.e. more than 42) digits.

There is also an algebraic (composite) factor of
16^137-1 that has 165 (i.e. more than 83) digits,
namely (16^137-1)/(2^2-1).

In your first posting on this subject
http://tech.groups.yahoo.com/group/primenumbers/message/22507
you courteously acknowledged my hints
(which I had hoped would resolve any ambiguity):

> Hints for the exercise:
> The 6 non-unit /algebraic/ factors of
> 16^137-1 = f1*f2*f3*f4*f5*f6
> may be found in one's head; no need for a computer.
> The largest, f6, has 42 digits, yet may be written in 7 characters.
> The next-to-largest, f5, may be written in 12 characters.

In that sense, the answer is 42.

In a more general sense, there are 62 non-unit proper
algebraic divisors ranging from 2^2-1 to (16^137-1)/(2^2-1),
with the following digit-counts:

  f1 = 2^2-1;
  f2 = 2^2+1;
  f3 = (2^137+2^69+1)/(2^2+1);
  f4 = (2^137+1)/(2+1);
  f5 = 2^137-2^69+1;
  f6 = 2^137-1;
  F = [f1,f2,f3,f4,f5,f6];
  V = vector(165);
  for(k=1,62,V[#Str(prod(j=1,6,F[j]^binary(64+k)[j+1]))]++);
  for(i=1,165,if(V[i],print(i"-digit algebraic divisors: "V[i])));

1-digit algebraic divisors: 2
2-digit algebraic divisors: 1
41-digit algebraic divisors: 2
42-digit algebraic divisors: 12
43-digit algebraic divisors: 2
82-digit algebraic divisors: 4
83-digit algebraic divisors: 16
84-digit algebraic divisors: 4
123-digit algebraic divisors: 2
124-digit algebraic divisors: 12
125-digit algebraic divisors: 2
164-digit algebraic divisors: 1
165-digit algebraic divisors: 2

Best regards

David

----- Mensaje reenviado ----
De: dgdegiorgi <degiorgi@...>
Para: Sebastian Martin Ruiz <s_m_ruiz@...>
Enviado: mié,2 febrero, 2011 19:13
Asunto: Re: Conjecture for triplets of primes

The Ruiz conjecture is independent with the Goldbach conjecture, as it does also
involve the position of the primes and not only their value.

Tn,1 contains three consecutive primes, Tn,2 contains first third and fifth of
five consecutive primes, and so on.

Unfortunately the conjecture seems to be false and some candidates for
counterexamples are 227, 2099, 5641.

227 is p_49, and it is easy to verify that T49,k (k=1..48) is not symmetric,
thus 229 does not appear as the middle element of a symmetric Tn,k.

All T49-k,k are also not symmetric and thus 227 daes not appear as the largest
element of a symmetric Tn,k.

The Tn,k with 227 as smallest element for k=1..4 are

                          227, 229, 233, -2


                          227, 233, 241, -2


                          227, 239, 257, -6


                          227, 241, 269, -14

with the fourt value the distance of 2pn from the sum of the other primes. for k
= 1000..10000 in step of 1000 we get

                      227, 8377, 17881, -1354

                      227, 17881, 38351, -2816


                      227, 27943, 59879, -4220


                      227, 38351, 82307, -5832


                      227, 49121, 105337, -7322


                      227, 59879, 128683, -9152


                      227, 71191, 152293, -10138


                      227, 82307, 176557, -12170


                      227, 93763, 200867, -13568


                    227, 105337, 225343, -14896

As the distance alway grows it should not be too difficult to prove that
equality can not be attained.

Daniel


--- In primenumbers@yahoogroups.com, Sebastian Martin Ruiz <s_m_ruiz@...> wrote:
>
> Examples:
>  
> n= 6 k= 2 {7,13,19}     7+19=13*2
> n= 7 k= 2 {11,17,23}   11+23=17*2
> n= 10 k= 3 {17,29,41}       " "
> n= 10 k= 5 {11,29,47}
> n= 11 k= 3 {19,31,43}
> n= 12 k= 6 {13,37,61}
> n= 13 k= 3 {29,41,53}
> n= 13 k= 4 {23,41,59}
> n= 16 k= 1 {47,53,59}
> n= 16 k= 7 {23,53,83}
> n= 17 k= 7 {29,59,89}
> n= 18 k= 4 {43,61,79}
> n= 19 k= 8 {31,67,103}
> n= 20 k= 3 {59,71,83}
> n= 20 k= 4 {53,71,89}
> n= 20 k= 10 {29,71,113}
>
>
> Note: I did not find any example for the prime number 227.
>  
> Sincerely
>  
> Sebastián Martín Ruiz
>
> ________________________________
>
> De: Carlos Rivera <cbrfgm@...>
> Para: Sebastian Martin Ruiz <s_m_ruiz@...>
> Enviado: dom,30 enero, 2011 01:57
> Asunto: Re: Conjecture for triplets of primes
>
> 2011/1/29 Sebastian Martin Ruiz <s_m_ruiz@...>
>
> Hello all:
> >
> >Let's consider the triplet of prime numbers: Tn,k = {p (n+k), pn, p (n-k)}  k
><n
> >positive integers.
> >
> >We will say that Tn,k is symmetric if p(n+k) +p (n-k) =2pn.
> >( pi= is the i-th prime number).
> > 
> >Conjecture:
> > 
> >For all q>2 prime number exists n, k such that q is in the simmetric Tn,k.
> > 
> > 
> >Sincerely:
> > 
> >Sebastián Martin Ruiz
> >
>
>
>
> --
> C.Rivera
> www.primepuzzles.net
> cbrfgm@...
>
>
> Examples?
>
>
>
>
> [Non-text portions of this message have been removed]
>




[Non-text portions of this message have been removed]

Let F be a finite set of prime numbers. Is it sure that a prime number p exists
such that, whenever 2p is the sum of two prime numbers, none of them belongs to
F?

Hi David,
--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
>
>
> --- In primenumbers@yahoogroups.com,
> "kraDen" <kradenken@> wrote:
>
> > My question is how does one know algebraically
> > (or at least without trial dividing) that
> > 2^2+1 divides 2^137+2^69+1
>
> We want to show that y = 2^2 + 1 divides N = 2^137 + 2^69 + 1.
> Let u = 2^68. Then
> N - y = 2*u^2 + 2*u - 2^2 = 2*(u-1)*(u+2).
> But y divides u - 1  = (y-1)^34 - 1. Hence y divides N - y.
> Hence y divides N and we are done.
Thankyou.
However this seems to be proving it is after already knowing it is (hopefully
that statement is understandable).
However this still doesn't explain to to me how you (algebraically) knew that
2^2+1 was a divisor.
Instead it looks like you have achieved the factor by trial division and then
proved it algebraically.

cheers
Ken


> Note that we do not need to compute the value of 2^2+1.
> I believe that I can do that in my head, but fortunately
> it is not necessary for this algebraic exercise :-)
>
> David
>

Actually, the original number 16^137-1 is equal to 2^548-1, correct?

x^548-1 is easily seen to be divisible by x^4-1, which is divisible
by x^2+1.

So 2^548-1 is divisible by 2^2+1.



On 2/2/2011 3:08 PM, kraDen wrote:
> Hi David,
> --- In primenumbers@yahoogroups.com, "djbroadhurst"<d.broadhurst@...>  wrote:
>>
>>
>>
>> --- In primenumbers@yahoogroups.com,
>> "kraDen"<kradenken@>  wrote:
>>
>>> My question is how does one know algebraically
>>> (or at least without trial dividing) that
>>> 2^2+1 divides 2^137+2^69+1
>>
>> We want to show that y = 2^2 + 1 divides N = 2^137 + 2^69 + 1.
>> Let u = 2^68. Then
>> N - y = 2*u^2 + 2*u - 2^2 = 2*(u-1)*(u+2).
>> But y divides u - 1  = (y-1)^34 - 1. Hence y divides N - y.
>> Hence y divides N and we are done.
> Thankyou.
> However this seems to be proving it is after already knowing it is (hopefully
that statement is understandable).
> However this still doesn't explain to to me how you (algebraically) knew that
2^2+1 was a divisor.
> Instead it looks like you have achieved the factor by trial division and then
proved it algebraically.
>
> cheers
> Ken
>
>
>> Note that we do not need to compute the value of 2^2+1.
>> I believe that I can do that in my head, but fortunately
>> it is not necessary for this algebraic exercise :-)
>>
>> David
>>
>
>
>
>
> ------------------------------------
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
> Yahoo! Groups Links
>
>
>
>
>

--- In primenumbers@yahoogroups.com,
Jack Brennen <jfb@...> wrote:

> Actually, the original number 16^137-1 is equal to 2^548-1,
> correct? x^548-1 is easily seen to be divisible by x^4-1,
> which is divisible by x^2+1.
> So 2^548-1 is divisible by 2^2+1.

Thanks Jack for explaining to my good friend Ken,
who had seemed to believe that I had cheated
by computing (shame!) the integer 2^2+1 and
then actually using trial division (crime!)
by whatever integer 2^2+1 turned out to be.
I never did any such heinous thing, honest, Guv.

David

--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> 16^137-1 = f1*f2*f3*f4*f5*f6
where
> f1 = 2^2-1
> f2 = 2^2+1
> f3 = (2^137+2^69+1)/(2^2+1)
> f4 = (2^137+1)/(2+1)
> f5 = 2^137-2^69+1
> f6 = 2^137-1

Exercise 2: Without using a computer, prove
that every divisor of f3, f4, f5 and f6
is congruent to 1 modulo 137.

David

yes, because gaps between prime numbers grow arbitrarily large.
Maximilian

On Wednesday, February 2, 2011, Dimiter Skordev
<skordev@...> wrote:
> Let F be a finite set of prime numbers. Is it sure that a prime number p
exists such that, whenever 2p is the sum of two prime numbers, none of them
belongs to F?
>
>