Primality Formula Conjecture

Primality Formula Conjecture

To test any $$(6x-1)$$ numbers for primality.

$$4^{3x-1} \bmod (6x-1)$$

If that is equal to 1 then $$(6x-1)$$ is prime.

To test any $$(6x+1)$$ numbers for primality.

$$4^{3x} \bmod (6x+1)$$

If that is equal to 1 then $$6n+1$$ is prime.

I am unsure if this holds true for infinity. I have only tested around 200 numbers by hand. It quickly becomes difficult because of the exponent, and I am also not a professional Mathematician, I just like to play with numbers. So please be patient with me.

Backstory

I stumbled upon this while fooling around with numbers and the Collatz conjecture. I was first studying

$$\frac{3x+1}{2}$$

After which I became interested in finding what numbers of $$x\bmod 6 = 5$$ or $$x\bmod 6 = 1$$ became a power of 2 within the Collatz Conjecture. So I shifted things around a bit and create this formula.

$$y = \frac{2^{x}-1}{3}$$

That resulted in this series.

X Y
1 $$\frac{1}{3}$$
2 $$1$$
3 $$2\frac{1}{3}$$
4 $$5$$
... ...

This was too noisy with fractions every other result, so I removed the noise by using 4.

$$y = \frac{4^{x}-1}{3}$$

X Y
1 $$1$$
2 $$5$$
3 $$21$$
4 $$85$$
... ...

I then became interested in knowing the factors of those numbers.

X Y Prime Factors
1 $$1$$ 1
2 $$5$$ 5
3 $$21$$ 3, 7
4 $$85$$ 5, 17
5 $$341$$ 11, 31
6 $$1365$$ 3, 5, 7, 13
7 $$5461$$ 43, 127
8 $$21845$$ 5, 17, 257
9 $$87381$$ 3, 7, 19, 73
10 $$349525$$ 5, 11, 31, 41
11 $$1398101$$ 23, 89, 683
... ... ...

I then noticed a pattern and created this formula.

$$\frac{4^{3x-1}-1}{3}$$

X Y Prime Factors
1 $$5$$ 5
2 $$341$$ 11, 31
3 $$21845$$ 5, 17, 257
4 $$1398101$$ 23, 89, 683
5 $$89478485$$ 5, 29, 43, 113, 127
6 $$22906492245$$ 1, 3, 5, 7, 13, 19, 37, 73, 109
... ... ...

I noticed when $$\frac{4^{3x-1}-1}{3}$$ was divisible by $$(6x-1)$$ then it was a prime number. I then continued testing this conjecture with hundreds of primes. It seemed to work.

I don't know how to go about proving this. I'm not practiced in proofs being just a math hobbyist. It would be amazing to hear your feedback about this conjecture.

• Fermat's little theorem says if $6n-1$ is prime then $4^{3n-1}=2^{(6n-1)-1}\equiv1\pmod{6n-1}$ Commented Jul 9, 2021 at 20:40
• but there are pseudoprimes like $341=6\times57-1$, which is not prime $(31\times11)$ but $2^{6\times57-2}=4^{3\times57-1}\equiv1\pmod{6\times57-1}$ Commented Jul 9, 2021 at 20:43
• The second claim is false for $x=184$, which gives $6x+1=1105=5 \cdot 13 \cdot 17$, a pseudoprime to base $2$. See oeis.org/A001567.
– lhf
Commented Jul 9, 2021 at 20:54
• It is impressive that you stumbled across the notion of a pseudoprime by accident, and realised intuitively that there is a connection to primes.
– tkf
Commented Jul 9, 2021 at 21:01

If $$p=6x-1$$ is prime,
then by Fermat's little theorem $$4^{3x-1}=2^{6x-2}=2^{(6x-1)-1}\equiv 1\pmod{6x-1}$$.
But the converse does not hold for a pseudoprime base $$2$$ such as $$341=6\times57-1$$:
$$4^{3\times57-1}=2^{(6\times57-1)-1}=2^{340}\equiv1\pmod{341=6\times57-1}$$,
though $$341=11\times31$$ is not prime.