Re: Small prime divisors of very large numbers
- --- In firstname.lastname@example.org, "richard_in_reading" <richard_in_reading@...> wrote:
>No, it's not actually.
> --- In email@example.com, "Mike Oakes" <mikeoakes2@> wrote:
> > Here's a Lemma that should be both true and useful.
> > For any non-zero integer q, define b(q,n) by the recurrence relation
> > b(q,n+1)=q^b(q,n), with initial condition b(q,0)=1.
> > [So b(q,1)=q, b(q,2)=q^q, and so on.]
> Isn't this equivalent to the not very interesting observation that x divides x^y when x and y are nonzero integers?
If you set x=b(q,n), then b(q,n+1)=q^x, NOT x^y for some y, so your observation does not apply.
But I do agree I didn't need an inductive proof: David's observation is the one to use.
- Dear all,
I come back to this topic, looking for a working "pow_mod".
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^(a^(a^ ... ^(a[k-1]^a[k]) ... ) modulo m
where the modulus "m" need not be prime.
Although this may work for prime m
(at least, pmod([2,2,2],5) = Mod(1,5) as should),
= Mod(1, 4)
which is most certainly wrong.
So, to put it short, has anyone a working pmod() in his "library" ?
Thanks in advance!
--- In firstname.lastname@example.org, "David Broadhurst"
I consider that his code should not be trusted.