# What is the ratio of Carmichael pseduo-primes to true primes for $1$ to $n$? Or is it known?

Let $$\pi(n)$$ be the prime counting function. And let $$\varphi(n)$$ be the count of Carmichael pseudo-primes for $$1$$ to $$n$$. Is the ratio,

$$\frac{\varphi(n)}{\pi(n)}$$

is known, as $$n \to \infty$$? I am asking this because of i want to know how much safe is the Fermat Primality Test (the one which only uses Fermat's Little Theorem).

I recently wrote a Python script (initially for RSA) and produced more than 10, random 1024 bit primes with the help of this test. After i used the powerful mathematical software PARI/GP to check if they are really primes or pseudo-primes. In conclusion none of them were pseudo-primes. So, if know this rate, i will know the probability that this test will encounter a pseudo-prime and fail.

## 1 Answer

We have the following result (Knödel, $$1953$$) :- $$\varphi(n) By strengthened version of PNT, we will have for sufficiently large $$n$$: $$\pi(n)>\frac{n}{\log n}$$ Thus $$\forall$$ sufficiently large $$n$$, we have:- $$\frac{\varphi(n)}{\pi(n)}<\log n \exp\big(-k(\log n \log\log n)^\frac{1}{2}\big)=\exp \big(\log \log n -k(\log n \log\log n)^\frac{1}{2}\big)$$ Note that:- $$\lim_{n \to \infty} \log \log n -k(\log n \log\log n)^\frac{1}{2}=- \infty \implies \lim_{n \to \infty} \exp \big(\log \log n -k(\log n \log\log n)^\frac{1}{2}\big)=0$$ Hence, we have:- $$\lim_{n \to \infty}\frac{\varphi(n)}{\pi(n)}=0$$

• Hence we can say Fermat's primality test is pretty safe since there is almost no possibility to a randomly selected 1024 bit (in other words, 128 digit in base 10) number to be a pseudo prime. – İbrahim İpek Jul 16 at 14:46
• More than 128 digits indeed... So it is even safer for this case. – İbrahim İpek Jul 16 at 17:37