Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

18
votes
2answers
830 views

What is the millionth decimal digit of the (10^10^10^10)th prime?

What is the millionth decimal digit of the $10^{10^{10^{10}}}$th prime? (This prime is, of course, far larger than the largest currently "known" prime, the latter having nearly 13 million ...
4
votes
1answer
92 views

What is the probability of picking a random prime < n?

If I shoot in the dark and pick a random number that's $<n$, what's the probability that the number will be prime? How many guesses, on average, would it take to get a prime number? I would really ...
1
vote
1answer
428 views

If $n$ is an odd pseudoprime , then $2^n-1$ is also odd pseudoprime

I have some problems understanding the following proof: Definition: A composite number $n \in \mathbb{N}$ is called pseudo prime if $n \mid 2^{n-1}-1$ holds. Theorem: If n is a odd pseudo prime ...
0
votes
1answer
129 views

Is there a closed form to $a^b \bmod b$ if $b$ is not a prime?

We know $$a^p \equiv a \pmod p\quad p\text{ a prime, }0\leq a \leq p-1.$$ But if we have $b$, not prime, what's the new formula? $$a^b \equiv\ ? \pmod b,\quad b\text{ not a prime, } 0\leq a \leq ...
2
votes
3answers
398 views

Proof: if $n=pq$ then $p-1\mid q-1$ and $q-1\mid p-1$

Now I'm asking my first question to understand a specific proof: Let $n=pq$ and $q,p \in \mathbb{P}$. Then we get $p-1\mid n-1$ and $q-1\mid n-1$, because there are prime integers mod $p$ and mod ...
6
votes
0answers
124 views

Number of primefactors in $ f(n,W) = \prod_{k=1}^W (p_k^n -1) \text{ where } p_k=Prime(k) $

I'm reviving an old fiddling, although I do not yet really see its benefit. Beginning with the eulerproduct for the zeta-function in the representation $\small \zeta(n)=\prod {1\over 1-p^{-n} } = ...
7
votes
3answers
512 views

What is the largest $n$ for which the $n$th prime is known?

$p = 2^{43,112,609} - 1$ is currently the largest known prime, but the $n$ for which this $p$ is the $n$th prime is, presumably, unknown. What is the largest $n$ for which the $n$th prime is known? ...
5
votes
2answers
324 views

RSA encryption. Breaking 2048 keys with index

I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic. I ...
1
vote
1answer
161 views

Primes and probabilities

Imagine a set $S$ of $10^{12}$ consecutive integers $n, n + 1, n + 2, n + 3, \ldots, n + 10^{12}-1$, where the exact identity of $n$ will be partially determined randomly as described below, and ...
8
votes
1answer
470 views

Can $x^{n}-1$ be prime if $x$ is not a power of $2$ and $n$ is odd?

Are there any solutions to $x^{n}-1=p$ with p prime, integers $x,n>1$ and $x$ not a power of $2$? $x$ must be even. $n$ is odd since if $n=2m$ then $p=x^{n}-1=(x^{m}+1)(x^{m}-1)$ hence $p=x^{m}+1$ ...
34
votes
2answers
1k views

Small primes attract large primes

$$ \begin{align} 1100 & = 2\times2\times5\times5\times11 \\ 1101 & =3\times 367 \\ 1102 & =2\times19\times29 \\ 1103 & =1103 \\ 1104 & = 2\times2\times2\times2\times ...
6
votes
1answer
375 views

Combinatorial interpretation of the Prime Number Theorem?

One version of the Prime Number Theorem is that $p_n \sim n \ \ln \ n$, while by Stirling's formula $\ln(n!) \sim n \ \ln \ n$; consequently, $p_n \sim \ln(n!)$, $\rm \color{red}{\text{and } e^{-p_n} ...
1
vote
0answers
237 views

Easiest way to prove that a subset of even integers is closed under multiplication?

What's the easiest way of showing that; $2\mathbb{Z}\setminus (4n-2)\mathbb{Z}$ is closed under multiplication? (I'm trying to show that $(4n-2)$ is a prime element of $2\mathbb{Z}$ by showing ...
9
votes
1answer
370 views

Question about a proof in Iwaniec-Kowalski's Analytic Number Theory book

My question is about the end of the proof of theorem 1.1, in page 27. Namely, it is stated that whenever we have a multiplicative function $f:\mathbb{N} \to \mathbb{C},$ let the sequence ...
2
votes
2answers
967 views

How many ordered pairs of positive integers

For a prime integer p, how many ordered pairs of positive integers (a, b) are there that satisfy $$\frac{1}{a} + \frac{1}{b} =\frac{1}{p}$$ For example, for p = 5, $$\frac{1}{6} + ...
5
votes
0answers
154 views

Proof of infinitude of primes whose reversal in base 10 is also prime

Is there any proof of infinitude of http://oeis.org/A007500 primes. If you want to generate them here is trivial and naive python program. ...
3
votes
2answers
312 views

Minimal dense subset of $\mathbb{Q} \cap [0,1]$

The following question was a problem in an Analysis exam: Let $n \in \mathbb{N}$. Define $A_{n} := \displaystyle \left\{\frac{k}{2^n} \bigg| k \in \mathbb{Z}, 0 \leq k \leq 2^n \right\}$. Let ...
4
votes
1answer
193 views

Algorithm for keeping a concrete version of Euclid's argument simple

(My actual question is at the very bottom of this posting.) Suppose you're teaching a course in mathematics-for-liberal-arts majors and it's the last math course they'll ever take. It has almost no ...
11
votes
1answer
289 views

Is there any theoretical indication that this conjecture of Catalan could be true?

Belgian mathematician Catalan in $1876$ made next conjecture: If we consider the following sequence of Mersenne prime numbers: $2^2-1=3 , 2^3-1=7 , 2^7-1=127 , 2^{127}-1$ then $$2^{2^{127}-1}-1$$ is ...
1
vote
2answers
784 views

Factoring n, where n=pq and p and q are consecutive primes

So in RSA, there is a modulus n which is the product of two primes. My question is regarding when p and q are consecutive primes, what would the time complexity be? So, n=pq and p and q are ...
3
votes
2answers
210 views

Split prime in $\mathbb{Z}[\sqrt{14}]$

I have this assertion: if $p$ is a prime such that $p\equiv 11 \pmod{56}$, then $p$ splits in $\mathbb{Z}[\sqrt{14}]$ (the discriminant of $\mathbb{Z}[\sqrt{14}]$ is $56$.) Why? Does $p\equiv ...
1
vote
1answer
125 views

Tile $\mathbb{R}^n$ with Primitive Cuboids

For every integer $n$ with $i$ prime factors associate a unique tile in $\mathbb{R}^m$ with $m \ge i$ as such, for every prime factor $p_j$ of $n$, the tile is a cuboid of dimension $m$ with a ...
12
votes
3answers
495 views

Twin primes of form $2^n+3$ and $2^n+5$

How to prove that $2^n+3$ and $2^n+5$ are both prime for only finitely many integers $n$? And how to prove that there are infinitely many primes of the form $2^n+3$ and $2^m+5$
5
votes
1answer
96 views

Primes of the form $p_{i_1}p_{i_2}\cdots p_{i_n}+2k$

Let $S_{n,k}$ be the set of all numbers that can be written as the product of $n$ odd primes plus $2k$. Is there integers $n>1$ and $k>1$ such that $S_{n,k}$ contains finite number of primes?
7
votes
3answers
343 views

Which is the most restrictive closed-form expression that still generates all primes?

"The set $\{f(n)\}, n=1,2,\ldots$ includes all primes except a finite number of exceptions." This statement is true for $$f(n)=\sqrt{1+24n},$$ for which the exceptions are 2 and 3. It also generates ...
-3
votes
1answer
95 views

primes proofs observations [closed]

1) Taking $p_1,p_2,\dots,p_k$ to be the primes up to $x^{1/2}$ we have a way to determine, with proof, each prime $N$ between $x^{1/2}$ and $x$ by Finding a representation of $N$ as in part c. Find ...
2
votes
1answer
95 views

For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$

I'm having a bit of difficulty writing a graceful proof for the following problem: For a prime $p$, determine the number of positive integers whose greatest proper divisor is $p$. Let $A$ be the ...
2
votes
1answer
104 views

With what probability is this polynomial equal to zero (mod a prime $p$)?

If we suppose that we have a polynomial $q(x)$ of the following form: $q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$ In other words, if we are given a polynomial with binary ...
1
vote
0answers
74 views

lower bounds for maximum computing times for integer factorisation

Supposing that n were known to have two prime factors, and that the computer had a database of all the primes $<\sqrt{n}$. Then, unless n is square, one factor would be $<\sqrt{n}$. If an ...
-2
votes
1answer
108 views

Primes classifications [closed]

1) If $p_1$$p_2$,...,$p_k$ be different primes and m = product of primes $p_1$,$p_2$,...,$p_k$ . How to prove that, when N = $N_1$ + $N_2$+...+$N_k$, where the prime factors of $N_i$ (here i is ...
11
votes
2answers
422 views

Asymptotics of LCM

Let $\operatorname{LCM}(x_1,x_2,\ldots,x_n)$ be the least common multiple of the integers $x_i$. How can one find the asymptotics of $\operatorname{LCM}(f(1),f(2),\dots,f(n))$ as $n$ approaches ...
3
votes
3answers
2k views

Riemann Hypothesis and prime number distribution

I do not grasp all concepts of the Riemann Hypothesis (better yet: as a layman I barely grasp anything...). However, I understand that there is a certain link between the Riemann Hypothesis and prime ...
4
votes
1answer
223 views

$16$ natural numbers from $0$ to $9$, and square numbers: how to use the pigeonhole principle?

There are $16$ natural numbers placed next to each other. Each is a number from $0$ to $9$. These are in any order, and you can have as many repeats as you want (e.g. all $16$ numbers can be zero, or ...
3
votes
2answers
328 views

Primes and proofs

1) Are there infinitely many primes of the form $a_n$? if $p_1 = 2 < p_2 = 3 <\cdots$ is the sequence of primes then are there infinitely many $n$ for which $p_1p_2\dots p_n + 1$ is prime? For ...
1
vote
2answers
382 views

Ratio of primes

How can one find the limit as M approaches infinity of the ratio of the number of primes p to the number of primes q all less then M. Where every p satisfy: p+42 is prime, and p+20 is prime. And ...
14
votes
2answers
462 views

Primes sum ratio

Let $$G(n)=\begin{cases}1 &\text{if }n \text{ is a prime }\equiv 3\bmod17\\0&\text{otherwise}\end{cases}$$ And let $$P(n)=\begin{cases}1 &\text{if }n \text{ is a prime ...
4
votes
2answers
189 views

How to prove this inequality using prime number theorem

Define $s_n=p_{n+1}-p_n$, where $p_n$ is the $n$th prime number, now how to show that $$\lim_{n \rightarrow \infty} \inf \frac{s_n}{\log n} \leq 1$$ I used the result from the prime number theorem: ...
3
votes
1answer
123 views

Formula for likely prime

Numbers of the form $n!+1$ are quite often prime numbers. Is there any formula $f(n)$ such that the probability that $f(n)$ is prime approaches 1 as $n$ goes to infinity and $f(n)$ also approaches ...
4
votes
1answer
150 views

An unbounded convex polyhedron realizing the primes?

Does there exist an unbounded convex polyhedron with faces that have 3, 5, 7, 11, 13, ... edges, i.e., such that the number of edges of each face realize exactly the odd primes, with each prime ...
4
votes
3answers
117 views

Given $a$, $b$, and a prime $p$, how fast can we solve $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$?

If we're given two naturals, $a$ and $b$, and a prime $p$, how fast can we find two more naturals such that $(a \cdot c) - (b \cdot d) \equiv 1 \bmod p$? Additionally, you are allowed to precompute ...
6
votes
1answer
151 views

Puzzle: Can you find an elementary proof that every $n \gt 6$ can be represented as a sum of $O(\log n)$ distinct primes?

Can you find an elementary proof that every $n \gt 6$ can be represented as a sum of $O(\log n)$ distinct primes? For example, $11 = 11$, $12 = 5 + 7$, $13 = 2 + 11$, $14 = 2 + 5 + 7$. On the other ...
5
votes
2answers
3k views

Fastest prime generating algorithm

What is the fastest known algorithm that generates all distinct prime numbers less than n? Is it faster than Sieve of Atkin?
10
votes
2answers
216 views

Probability p+k is a prime

If p is a prime number, and k is an even integer, what is the probability p+k is a prime number? According to my simulations p+108 is prime twice as often as p+344
3
votes
3answers
226 views

Convergence of prime series

Where can I read about convergence of series constituted of prime number such as the following: $$\sum_p \frac{1}{p (\log{p})^\alpha}\;?$$ How does convergence depend on $\alpha$?
5
votes
0answers
199 views

Sums of Dirichlet-Characters over prime numbers (part 2)

This is kind of related to my previous question that was poorly stated because of misreading my own notes that I have taken on the papers I am currently reading, so no surprise that it eventually ...
7
votes
1answer
194 views

Asymptotics of sums of Dirichlet-Characters over prime numbers

Again in relation with some stuff I am currently reading, the authors make use of the following "standard argument in prime number theory": Let $\chi$ be a non-principal Dirichlet-character. Then ...
4
votes
0answers
344 views

Sum of odd prime and odd semiprime as sum of two odd primes?

How to prove that each sum of odd prime and odd semiprime can be written as sum of two odd primes $(p_1+p_2p_3=p_4+p_5)$ ? Since we know that each prime number greater than $3$ is of the form $6k\pm ...
1
vote
3answers
497 views

Can we use Peano's axioms to prove that integer = prime + integer?

Every integer greater than 2 can be expressed as sum of some prime number greater than 2 and some nonegative integer....$n=p+m$. Since 3=3+0; 4=3+1; 5=3+2 or 5=5+0...etc it is obvious that statement ...
4
votes
1answer
196 views

A finite sum of prime reciprocals

How can you prove that $\sum\limits_k \frac1{p_k}$, where $p_k$ is the $k$-th prime, does not result in an integer?
8
votes
2answers
1k views

Why does $\phi(pq)=\phi(p)\phi(q)$?

In an RSA paper I am reading it is assumed that where $p$ and $q$ are distinct prime numbers: $\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$ I would love to know why/how this is so? Is there some way to prove ...