P[random x is composite | $2^{x-1}$ mod $x = 1$ ]?

Question

Select a uniformly random integer $n$ between $2^{1024}$ and $2^{1025}$

(Q) What is the probability that n is composite given that $2^{n-1}$ mod $n = 1$ ?

How did you calculate this?

More info:

One way to calculate this would be if you had the following two variables:

$$P_Q(n) = 1 - { P_{prime}(n) \over P_{cong}(n) }$$

Where:

• $P_{prime}(n)$ is the probability n is prime
• $P_{cong}(n)$ is the probability that $2^{n-1}$ mod $n = 1$

So answering the following two questions would be sufficient to answer the main one:

What is $P_{prime}(n)$ equal to?

What is $P_{cong}(n)$ equal to ?

(This holds because the probability that n is prime if the congruence is false is 0.)

Based on the PouletNumber forumale given below:

exp((ln(2^1025))^(5/14))-exp((ln(2^1024))^(5/14))

= 123

and

(2^1025)*exp(-ln(2^1025)*ln(ln(ln(2^1025))) / (2*ln(ln(2^1025)))) -
(2^1024)*exp(-ln(2^1024)*ln(ln(ln(2^1024))) / (2*ln(ln(2^1024))))

= 9.82e263

So its between 123 < x < 9.82e263

??

And so $P_Q$ is:

3.29e-306 < P_Q < 2.63e-44

Answer 1

Due to Fermat's Little Theorem, $$ a^{p-1} \bmod p=1 $$ if $a$ and $p$ are coprime. In your case $a=2$ and $p$ are all other primes, as pointed out by tomasz in the comment.

But as I recognized right now you are looking for composite $x$, so you are looking for Fermat Pseudo primes. Their distribution can be found here. A file with pseudo primes up to $10^{15}$ can be found here.

They are also called Poulet numbers, and according to the MathWorld page, for large $x$ their number below $x$ is given by $$ \exp((\ln(x))^{5/14})<P_2(x)<x\exp\left(-\frac{\ln x \ln \ln \ln x}{2 \ln \ln x}\right). $$

If $P_2(x)$ is the same as your $P_{\text{cong}(x)}$, you have something to work with. But see my edit below for some other possible meanings of $P_2(x)$.

---

Concerning your edit: You can approximate $\pi(x)$, the number of primes below $x$ by $x/\log x$. So in the given range there are $$ \pi(2^{1025})- \pi(2^{1024})= 2^{1025}/(1025\log 2)- 2^{1024}/(1024\log 2)=3.74\cdot 10^{307} $$ primes.

---

EDIT

Here are some more facts about Poulet numbers:

• Rotkiewicz Theorem: If $n>19$, there exists a Poulet number between $n$ and $n^2$. The theorem was proved in 1965.

• Let $p$, $q$, $\ell$ be odd primes, and let $P_2(x)$ be the counting function for odd pseudoprimes with two distinct prime factors, $P_2(x) := \#\{n \leq x : n = pq, p < q, psp(n)\}$ (where $psp(n)$ means $n$ is pseudoprime). Then $P_2(x)\sim C\sqrt{x} / \ln^2(x)$ as $x\to \infty$.

  For more read here. The notation $P_2(x)$ (the counting function for odd pseudoprimes with $2$ distinct prime factors) seems to be a little confusing. In the last link they also state a result by Erdős, saying $c_1\log x\leq P_k(x)\le c_2\frac x{\log^k x}$. Maybe you need to sum the $P_k(x)$ to get to what you need.