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

> it's notable that the pop-in, pop-out, pop-in prime
> 3686183, in Richard Heylen's message
> http://tech.groups.yahoo.com/group/primenumbers/message/20545
> is one for which one needs to be more careful

So let's go very slowly and hope not to fool ourselves.
I shall use "znorder" in preference to "eulerphi",
since then we shall see just how pretty Richard's prime is:

p=3686183;
a=Mod(137,p);q=znorder(a);
b=Mod(137,q);r=znorder(b);
c=Mod(137,r);s=znorder(c);
d=Mod(137,s);t=znorder(d);
e=Mod(137,t);u=znorder(e);
print([e,u])

[Mod(137, 2194), 137]

Aha! The order of 137 modulo 2194 is 137,
since the smallest integer u for which
137^u = 1 mod 2194
is u = 137. How nice. No problem living with that.

Now let's use Richard's constant, k = 2136727. He claims that

137^(137^(137^137)) + k is divisible by p
137^(137^(137^(137^137))) + k is NOT divisible by p
137^(137^(137^(137^(137^137)))) + k is divisible by p

We can quickly check those 3 claims:

k=2136727;
print(a^lift(b^lift(c^137))+k)
Mod(0, 3686183)

print(a^lift(b^lift(c^lift(d^137)))+k)
Mod(1803441, 3686183)

print(a^lift(b^lift(c^lift(d^lift(e^137))))+k)
Mod(0, 3686183)

But what happens at subsequent powerings?
It's clear: e = Mod(137, 2194) has order u = 137. Hence
lift(e^137) = 1
lift(e^(137^137)) = 1
lift(e^(137^(137^137))) = 1
and so on, ad infinitum.

Here there is no "gcd problem".
Richard hit a infinite gold mine of proofs:
for any number of 137's greater than 5,
the "powering" gives the same residue, modulo p, namely
a^lift(b^lift(c^137)),
obtained when the number of 137's is n=4.

Note that p did not really "pop in" at n=4.
We deliberately chose k to make p a divisor at n=4.
Then it *must* pop back at n=6, and stay for *ever* because
137^137 = 1 mod t, where
t = z(z(z(z(p)))), with
z(x) = znorder(Mod(137,x))

Check:

p=3686183;
z(x)=znorder(Mod(137,x))
t=z(z(z(z(p))));
if(Mod(137,t)^137==1,print("Alles klar"))
Alles klar

Finally, let's prove that "my" prime stays for ever:

print(z(z(z(z(z(z(67525153)))))))
1

David