Higher order Wierferich prime pairs

[carpetpool]

Suppose odd primes p and q are Wierferich prime pairs of order k if and only if:

p^(q-1) = 1 modulo q^k

q^k = 1 modulo p

where p ≠ 1 modulo q, q ≠ 1 modulo p, or equivalent restriction k > 1.

The first such pair (p,q) of order k = 2 is (3,11) because

3^10 = 1 modulo 11^2 and 11^2 = 1 modulo 3

The first pair of order k = 3 is (19,7) because

19^6 = 1 modulo 7^3 and 7^3 = 1 modulo 19

Which is the first such prime pair (p,q) or order k = 4, in other words primes p, q such that

p^(q-1) = 1 modulo q^4 and q^4 = 1 modulo p

It is easy to find any such primes p, q obviously is it not, but what are the smallest such primes?

What about orders k = 5, 6, 7 and so on?

It doesn't seem that easy to find such pairs as (3,11) k = 2 and (19,7) k = 3 are rare cases.

[wblipp]

The more general case of b^(q-1)=1 mod q^k (that is, not requiring b to be prime and not requiring the second congruence) is studied under the name Fermat Quotients (among other names). Have you tried mining tables of these results for cases that satisfy your additional constraints? Google led me to this stackexchange post, from which I soon came to this list. If not directly useful, perhaps searching this subject will turn up additional ideas to help you.

[science_man_88]

Originally Posted by carpetpool

Suppose odd primes p and q are Wierferich prime pairs of order k if and only if:

p^(q-1) = 1 modulo q^k

q^k = 1 modulo p

When p and q are odd, we get the equivalents:

p^(q-1)= 1 mod 2(q^k)

and

q^k= 1 mod 2p

plugging the second into the first we have

p^(2jp-2)= 1 mod 2((2jp-2)^k)= (2l+1) mod 2p
So 0= 2l+1 mod 2p where p^(2jp-2)=2l((2jp-2)^k)+1. EDIT: yes I'm partially wrong, I originally assumed q=1 mod p contrary to carpetpools rules.