### CoolManGame's blog

By CoolManGame, history, 11 months ago,

SAD NEWS: beepbeepboop has found 219781 to be a counter example :(( I was too excited that I forgot to check for big numbers. In fact there are quite many counter examples above 1e5. This conjecture is therefore proven to be false.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I unexpectedly found a simple primality condition when browsing the prime number sequence on OEIS. I thought it would be nice to share it here since I haven't seen it shared anywhere else. It's also easier to remember than the Miller-Rabin test. Here's some pseudocode to describe the primality test:

isPrime(N):
if N <= 10: return N in [2, 3, 5, 7]
return (Fib(N) % N == 1 or Fib(N) % N == N-1) and (2**(N-1) % N) == 1


(Note: (Fib(N) % N) and (2**(N-1) % N) can be evaluated in O(logn))

This does work, and I've gotten AC on https://www.spoj.com/problems/PON/ with it.

You can find this conjecture on https://oeis.org/A000040 where it said "Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n — 1) and 2^(n-1) mod n = 1}. — Gary Detlefs, May 25 2014". It's a conjecture, but conjectures are true in CP am I right lol.

I haven't found a name for it, nor have I seen it shared anywhere else. Though, if it's already known with a published name (I'm not the best googler lol), do let me know through the comments or DM.

• +127

 » 11 months ago, # |   0 Auto comment: topic has been updated by CoolManGame (previous revision, new revision, compare).
 » 11 months ago, # |   +31 Incredible. It also seems to be faster than Miller-Rabin.
 » 11 months ago, # |   +51 imagine inventing O(log n) primality test and publishing it only on oeis
 » 11 months ago, # |   0 It seems to be a heuristic primality test proposed by Selfridge.
•  » » 11 months ago, # ^ |   0 I did see it, but it seems like a different but similar test. The one I posted doesn't require p = 2 or -2 (mod 5)
 » 11 months ago, # |   +157 Sadly, it fails on $219781$ giving a false positive. $fib(219781) = 1$ $(\mod 219781)$ and $2^{219780} = 1$ $(\mod 219781)$ but $219781$ is a composite number equal to $271 \times 811$.You can check the calculation on Wolfram.
•  » » 11 months ago, # ^ |   +99 Man disproved a conjecture with just a for loop 💀
•  » » 11 months ago, # ^ |   0 OMG This is heartbreaking !!! :((( I was too excited after the AC on SPOJ, shouldve tried it with "Count Primes" on Leetcode. Later I'll update the post, and try the conjecture given below (there are two, though most likely it also fails). Sorry for this sadness :(( Thanks for pointing out the counter example
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +5 Bro if we do find one and it is posted publicly, then it is actually BAD NEWS! RSA Encyption wouldn't work and we would all be hacked... :(
•  » » » » 11 months ago, # ^ |   +9 Primality tests do not break RSA, since we do not actually find the prime factors of the number.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Looks like according to the link orz sent, you just won \$620!Edit: Oops, nevermind :(
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +8 unfortunately to claim the prize money the possible prime $p$ has to be equal to $\pm 2 \pmod{5}$ while $219781 = 1 \pmod{5}$ Source Edit: the hyperlink seems to not be working for me atleast, https://en.m.wikipedia.org/wiki/John_Selfridge#Selfridge's_conjecture_about_primality_testing
•  » » » » 11 months ago, # ^ |   +16 Challenge accepted! $22711873$ is one counterexample. It checks all the boxes: $22711873 \equiv -2$ $\pmod{5}$, $fib(22711873) \equiv 1$ $\pmod{22711873}$, $2^{22711873 - 1} \equiv 1$ $\pmod{22711873}$. However, $22711873$ is a composite number equal to $59 \times 349 \times 1103$. Calculations on Wolfram.
•  » » » » » 11 months ago, # ^ |   0 The wikipedia article and the blog seem to have different conditions for the primality test.The blog's condition is that:$fib(n) = \pm 1 \mod n \newline$ $2^{n-1} \equiv 1 \mod n \newline$While the PSW conjecture in the wikipedia article is that:$n \equiv \pm 2 \pmod{5}\newline$ $fib(n+1) = 0\mod n \newline$ $2^{n-1} \equiv 1 \mod n \newline$Your counterexample works for condition in the blog, but does not work for the actual PSW conjecture. Wolfram calculations: link
•  » » » » » » 11 months ago, # ^ |   0 Oops, you're right.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 That link gives a slightly different test. Note that it requires $p \equiv \pm 2 \pmod 5$ and $F_{p+1} \equiv 0 \pmod p$
 » 11 months ago, # |   0 What about numbers such that $n \equiv \pm 1 \mod 5$
 » 11 months ago, # |   +3
 » 11 months ago, # |   0 Auto comment: topic has been updated by CoolManGame (previous revision, new revision, compare).