Sorry, an error occurred while loading the content.

## Re: Small prime divisors of very large numbers

Expand Messages
• ... As might have been expected, Jens was the first to post what I believe to be the correct solution. Almost at the same time, Richard FitzHugh ... Like
Message 1 of 70 , Jun 30, 2009
"Jens Kruse Andersen" <jens.k.a@...> wrote:

> David Broadhurst wrote:
> > The first 7 primes that divide
> > 137^(137^(137^(137^137))) + 73
> > are 2, 3, 5, 29, 821, 23339, 67525153.
> >
> > Puzzle: Find the first 7 primes that divide
> > 137^(137^(137^(137^(137^137)))) + 73
>
> The same.

As might have been expected, Jens was the first
to post what I believe to be the correct solution.

Almost at the same time, Richard FitzHugh
sent me, privately, the same answer:

> I get the same first 7 primes to divide your larger number
> (namely 2, 3, 5, 29, 821, 23339, 67525153). This seems very
> strange indeed! It took about 6 minutes of actual processor
> time, after about 20 minutes of trying to accurately place
> all the brackets in the nested eulerphi calls!

Like Richard, I find this result to be "strange indeed".

Can anyone tell Richard and me why we should not be surprised?

With thanks to all concerned

David
• Dear all, I come back to this topic, looking for a working pow_mod . This : {mypmod(b,n,p)=local(m=[p],f=0); while(n=n-1,m=concat(eulerphi(m[1]),m));
Message 70 of 70 , Mar 23, 2014
Dear all,
I come back to this topic, looking for a working "pow_mod".
This :
{mypmod(b,n,p)=local(m=[p],f=0);
while(n=n-1,m=concat(eulerphi(m[1]),m));
for(p=n=1,#m,n=lift(Mod(b,m[p])^n);
if(f=f+(n*log(b)>=log(m[p])),n=n+m[p]));n%m[#m];}

yields:
mypmod(2,3,5)
= 2
but 2^2^2 % 5 = 16 % 5 = 1.
(and idem for 2^2^2^2 - of course.).

David gave some other code, in
:
"
Below is a Pari-GP procedure "pmod(a,m)" to compute
a[1]^(a[2]^(a[3]^ ... ^(a[k-1]^a[k]) ... ) modulo m
where the modulus "m" need not be prime.
(...)
{pmod(a,m)=local(k,q,t);k=#a;q=[m];t=a[k];
for(j=2,k-1,q=concat(eulerphi(q[1]),q));
for(j=1,k-1,t=Mod(a[k-j],q[j])^lift(t));t}
"
Although this may work for prime m
(at least, pmod([2,2,2],5) = Mod(1,5) as should),
it gives:

pmod([2,2,2],4)
= Mod(1, 4)
which is most certainly wrong.

So, to put it short, has anyone a working pmod() in his "library" ?

Maximilian