Smallest Strong Fibonacci Pseudoprime of Type I

From ProofWiki
Jump to navigation Jump to search

Theorem

The smallest strong Fibonacci pseudoprime of type I is $443 \, 372 \, 888 \, 629 \, 441$.


Proof

Let $N := 443 \, 372 \, 888 \, 629 \, 441$, to save writing it out in full each time.

From the definition of a strong Fibonacci pseudoprime of type I:

A strong Fibonacci pseudoprime of type I is a Carmichael number $N = \displaystyle \prod p_i$ such that an even number of the prime factors $p_i$ are of the form $4 m - 1$ where:

$(1): \quad 2 \left({p_i + 1}\right) \mathrel \backslash \left({N - 1}\right)$ for those $p_i$ of the form $4 m - 1$
$(2): \quad \left({p_i + 1}\right) \mathrel \backslash \left({N \pm 1}\right)$ for those $p_i$ of the form $4 m + 1$


We have that:

$N = 17 \times 31 \times 41 \times 43 \times 89 \times 97 \times 167 \times 331$

Of these, we see that:

\(\displaystyle 17\) \(=\) \(\displaystyle 4 \times 4 + 1\) which is a prime number of the form $4 n + 1$
\(\displaystyle 31\) \(=\) \(\displaystyle 4 \times 8 - 1\) which is a prime number of the form $4 n - 1$
\(\displaystyle 41\) \(=\) \(\displaystyle 4 \times 10 + 1\) which is a prime number of the form $4 n + 1$
\(\displaystyle 43\) \(=\) \(\displaystyle 4 \times 11 - 1\) which is a prime number of the form $4 n - 1$
\(\displaystyle 89\) \(=\) \(\displaystyle 4 \times 22 + 1\) which is a prime number of the form $4 n + 1$
\(\displaystyle 97\) \(=\) \(\displaystyle 4 \times 24 + 1\) which is a prime number of the form $4 n + 1$
\(\displaystyle 167\) \(=\) \(\displaystyle 4 \times 42 - 1\) which is a prime number of the form $4 n - 1$
\(\displaystyle 331\) \(=\) \(\displaystyle 4 \times 83 - 1\) which is a prime number of the form $4 n - 1$

Thus there are $4$ (an even number) of prime factors of $N$ of the form $4 n - 1$.


We note that:

\(\displaystyle N - 1\) \(=\) \(\displaystyle 288 \times 1 \, 539 \, 489 \, 196 \, 630\) and so $\paren {17^2 - 1} \divides \paren {N - 1}$
\(\displaystyle \) \(=\) \(\displaystyle 960 \times 461 \, 846 \, 758 \, 989\) and so $\paren {31^2 - 1} \divides \paren {N - 1}$
\(\displaystyle \) \(=\) \(\displaystyle 1680 \times 263 \, 912 \, 433 \, 708\) and so $\paren {41^2 - 1} \divides \paren {N - 1}$
\(\displaystyle \) \(=\) \(\displaystyle 1848 \times 239 \, 920 \, 394 \, 280\) and so $\paren {43^2 - 1} \divides \paren {N - 1}$
\(\displaystyle \) \(=\) \(\displaystyle 7920 \times 55 \, 981 \, 425 \, 332\) and so $\paren {89^2 - 1} \divides \paren {N - 1}$
\(\displaystyle \) \(=\) \(\displaystyle 9408 \times 47 \, 127 \, 220 \, 305\) and so $\paren {97^2 - 1} \divides \paren {N - 1}$
\(\displaystyle \) \(=\) \(\displaystyle 27 \, 888 \times 15 \, 898 \, 339 \, 380\) and so $\paren {167^2 - 1} \divides \paren {N - 1}$
\(\displaystyle \) \(=\) \(\displaystyle 109 \, 560 \times 4 \, 046 \, 850 \, 024\) and so $\paren {331^2 - 1} \divides \paren {N - 1}$

Thus for all $p \divides N$, we have that $\paren {p^2 - 1} \divides \paren {N - 1}$.


From Difference of Two Squares we have that:

$p^2 - 1 = \paren {p + 1} \paren {p - 1}$

and so for all $p \divides N$:

$\paren {p - 1} \divides \paren {N - 1}$

We also have that $N$ is square-free.

Thus by Korselt's Theorem, $N$ is a Carmichael number.


Now we also have that:

\(\displaystyle \paren {p^2 - 1}\) \(\divides\) \(\displaystyle \paren {N - 1}\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {p + 1} \paren {p - 1}\) \(\divides\) \(\displaystyle \paren {N - 1}\) Difference of Two Squares
\(\displaystyle \leadsto \ \ \) \(\displaystyle 2 \paren {p + 1} \paren {\frac {p - 1} 2}\) \(\divides\) \(\displaystyle \paren {N - 1}\) as $p - 1$ is even
\(\displaystyle \leadsto \ \ \) \(\displaystyle 2 \paren {p + 1}\) \(\divides\) \(\displaystyle \paren {N - 1}\)


Thus we have that:

$\forall p \divides N: 2 \paren {p + 1} \divides \paren {N - 1}$

This is actually stronger than the conditions for which $N$ is a strong Fibonacci pseudoprime of type I:

A strong Fibonacci pseudoprime of type I is a Carmichael number $N = \displaystyle \prod p_i$ such that an even number of the prime factors $p_i$ are of the form $4 m - 1$ where:

$(1): \quad 2 \left({p_i + 1}\right) \mathrel \backslash \left({N - 1}\right)$ for those $p_i$ of the form $4 m - 1$
$(2): \quad \left({p_i + 1}\right) \mathrel \backslash \left({N \pm 1}\right)$ for those $p_i$ of the form $4 m + 1$


It can be established by an exhaustive search that there are no smaller Carmichael numbers with this property.

Hence the result.

$\blacksquare$


Sources