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

> Richard hit a infinite gold mine of proofs

The next step is to look at cases with a Hardy-Wright
"gcd problem" that cannot be solved so easily and then
solve them with the Chinese Remainder Theorem (CRT).

I begin with base 137 and define
z(x) = znorder(Mod(137,x)).

The first problem prime is 823, with z(823) = 3*137.
So we have a "gcd problem" more difficult than Richard's.

Here is how to compute
137^(137^(137^(137^(137^137)))) modulo 823
with n = 6 occurrences of 137,
while keeping Hardy and Wright happy.

Let a=Mod(137,823) and b=Mod(137,3*137).
Then we need to compute
a^lift(b^c) with c=137^(137^(137^137)).
But we know that
lift(b^c) = 0 mod 137, and
lift(b^c) = 2 mod 3, since 137 = 2 mod 3, and c is odd.
Hence, by the CRT, lift(b^c) = 137 and
a^lift(b^c) = a^137 = Mod(174, 823).
But I used only the fact the c is odd. So the residue
with n > 1 occurrences of 137 has the constant value 174.

More generally, if we hit a factor 137 in a "znorder" chain,
we peel it off, and proceed with a "reduced" chain, using
the CRT. It may be that we later hit another factor of 137
in the reduced chain, which we can treat similarly.
For example, with p = 12018737 we have
z(z(z(p)/137))/137 = 10 with factors of 137 peeled
off at the first and third links of the chain.

Now suppose we hit a power of 137 greater than unity in a chain.
Consider, for example, the prime p = 5330399, with
z(z(p)) = 71*137^2. To compute
137^(137^(137^(137^(137^137)))) modulo p
we set a = Mod(137,p), b = Mod(137,z(p)), c = Mod(137,71*137^2)
and use the CRT to compute
a^lift(b^lift(c^d)), with d = 137^(137^(137)).
It's straightforward to compute Mod(137,71)^d using a reduced chain.
To show that Mod(137,137^2)^d = Mod(0,137^2) we need only the fact
that d >1. Hence the CRT will give us the value of lift(c^d).

Clearly these procedures require carefully programming.
The point of this contribution is to indicate
that there is no insuperable obstacle posed by
the "gcd problem", provided we use "znorder" and the CRT.

I conclude with the challenge set by Richard Heylen in
http://tech.groups.yahoo.com/group/primenumbers/message/20560
namely this: consider a powering of n instances of 2.
For what values of n is the residue modulo 3121 congruent to -5 ?

The order of Mod(2,3121) is 2^2*39. So we peel off 2^2
and study Mod(2,39), whose order is 2^2*3.
Then we peel off another 2^2 and are left with the easy
problem of powerings of 2 modulo 3, which give
Mod(2,3)^2 = Mod(1,3),
Mod(2,3)^(2^2) = Mod(1,3) and so on ad infinitum.
Hence, by two applications of the CRT, the answer
for n > 4 is the same as that for n = 4.
But it is trivial to check that
2^(2^(2^2)) + 5 = 0 mod 3121.
So we are done: all powerings with at least 4
instances of 2 give the same residue.

Morals:
1) When Hardy and Wright frown, think Chinese.
2) Blind iteration of "eulerphi" is fraught with danger.
3) "znorder" and the CRT enable us to tackle all such questions.

David