Testing prime numbers with modified Fermat's Little Theorem

Question

Is there a number $n$ such that:

• $6n-1$ is prime
• There exists a positive integer $r<3n-1$ such that $4^{r}\equiv1\pmod{6n-1}$

Answer 1

Run the following in a SAGE environment (or replace is_prime with your own primality testing function and run in a Python interpreter) to find examples:

n = 1
while n < 100:
    n = n+1
    k = 6*n - 1
    if is_prime(k)==1:
        r = 1
        while r < (3*n - 1):
            if 4**r%k == 1:
                print(n, k, r)
            r = r+1

With $k = 6n-1$, the first few triples $(n, k, r)$ it finds that satisfy $4^r \equiv 1 \pmod{k}$ and the prescribed conditions are:

(2, 11, 5)
(3, 17, 4)
(3, 17, 8)
(4, 23, 11)
(5, 29, 14)
(7, 41, 10)
(7, 41, 20)

Answer 2

For example, $$\eqalign{6n-1 = 17,& r = 4\cr 6n-1 = 41,& r = 10\cr 6n-1 = 89,& r = 11\cr 6n-1 = 113,& r = 14\cr 6n-1 = 137,& r = 34\cr 6n-1 = 233,& r = 29\cr }$$