1
$\begingroup$

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.

Thanks for reading.

$\endgroup$
4
  • 1
    $\begingroup$ Fermat's little theorem says if $6n-1$ is prime then $4^{3n-1}=2^{(6n-1)-1}\equiv1\pmod{6n-1}$ $\endgroup$ Commented Jul 9, 2021 at 20:40
  • 2
    $\begingroup$ 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}$ $\endgroup$ Commented Jul 9, 2021 at 20:43
  • 2
    $\begingroup$ 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. $\endgroup$
    – lhf
    Commented Jul 9, 2021 at 20:54
  • 3
    $\begingroup$ It is impressive that you stumbled across the notion of a pseudoprime by accident, and realised intuitively that there is a connection to primes. $\endgroup$
    – tkf
    Commented Jul 9, 2021 at 21:01

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Thanks for help. :) $\endgroup$ Commented Jul 9, 2021 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .