> --- In primenumbers@yahoogroups.com,

> "ronhallam@" <ronhallam@> wrote:

>

> > Work out the difference mod 6, 7 and 11 on the following number:

>

> 2203353588507632689540389884099234780425798106022737554148425561277092513841358286596173426627853446495163308636257511927689252306411

>

> In this case, n = p*q with (q-p) divisible by the primes

> 2, 3, 5, 7, 11, 4590011 and 186453571036492667910025371580824511.

>

> Puzzle: Use these data to find another prime that divides (q-p).

The answer is: 5558358186556723282830357110595686293

And here's the (ugly) code which found it:

n=<the long number>

v=[2, 3, 5, 7, 11, 4590011, 186453571036492667910025371580824511]

vv=[Mod(0,1)];for(k=1,#v,s=sqrt(Mod(n,v[k])); \

vv=concat(apply(x->[chinese(x,s),chinese(x,-s)],vv))); \

m=prod(k=1,#v,v[k]);vv=lift(vv); \

for(k=1,#vv,r=vv[k];s=(n-r^2)/m;apb=lift(Mod(s,m)/r); \

atb=(s-apb*r)/m; if(issquare(apb^2-4*atb), \

d=sqrtint(apb^2-4*atb); print(factor(d))))

Mat([5558358186556723282830357110595686293, 1])

Mat([5558358186556723282830357110595686293, 1])

(the answer is printed twice due to Mod(1,2) being equal to Mod(-1,2); if

you want to get rid of it, start the first loop with k=2 and initialize vv

to [Mod(1,2)] instead of [Mod(0,1)]).

> Comment: This puzzle may be solved, systematically, in less

> than 3 CPU-seconds, without appealing to extraneous data.

Puzzle solved? Check.

Systematically? Check.

Less than 3 CPU-seconds? Check.

Extraneous data? Unsure.

Elegant: Certainly not!

Peter