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

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?

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

-
+1 for not choosing $2^{2011}$ and $2^{2012}$...just kidding: interesting question. – draks ... Jul 26 '12 at 10:08
If $n$ is prime ($\neq 2$) then the congruence is always true. – tomasz Jul 26 '12 at 10:34
@tomasz: Your statement is correct, however it is not relevant. I have added more info above. – Andrew Tomazos Jul 26 '12 at 11:52
Technically one should not be subtracting upper bounds, but there's certainly room for grey area here. Neither bound is 100% guaranteed (no one has gone to the trouble of making "large enough $x$" explicit). With this proviso, the "safer" upper bound is to not subtract the $2^{1024}$ term at all. – Erick Wong Jul 27 '12 at 19:41

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.

-
The Prime Number Theorem tells you (roughly) how many primes there are in the range of interest. The estimates that draks cites tell you (roughly) how many composites there are, in the range of interest, satisfying the congruence. Isn't that all you need to know to answer your question? – Gerry Myerson Jul 26 '12 at 12:02
@user1131467 as Gerry pointed out, you've got enough information and you surely don't want me to do all the work for you, don't you? – draks ... Jul 26 '12 at 12:47
The two bounds you give for $P_2$ are not very close to each other, so you won't be able to get a number out of them. Nonetheless, this may be the best possible answer with current knowledge. – David Speyer Jul 26 '12 at 14:06
I've added calculations of your PouletNumber forumlae above. Can you please verify I have calculated the two bounds correctly? – Andrew Tomazos Jul 27 '12 at 6:41
If my calculations are correct than your answer is useless. The probability has been narrowed down between ~0.0 and 0.9. – Andrew Tomazos Jul 27 '12 at 6:48