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

3
votes
2answers
329 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
197 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
296 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
851 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
211 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
348 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 ...
2
votes
1answer
103 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
108 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
77 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
110 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
436 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
231 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
329 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
405 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
474 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
194 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
124 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
158 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
184 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 ...
6
votes
2answers
4k 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
218 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
229 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
217 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
202 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
369 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
529 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
199 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 ...
7
votes
2answers
306 views

Showing the equivalence of two forms of the Goldbach Conjecture

My number theory textbook has the following (paraphrased) exercise: Goldbach wrote a letter to Euler with the following conjecture: Every integer greater than five can be written as the sum of three ...
2
votes
2answers
281 views

How to show that $n$ is a prime?

Suppose that $n>1$ satisfies $(n-1)! \equiv -1 \pmod n$. Show that $n$ is a prime. (Hint: Antithesis) My own trying: $n=3$: $(3-1)!+1= 3 \cdot 1$ => $3|2!+1$. $n=5$: $(5-1)!+1=25 = 5 \cdot 5$ ...
8
votes
3answers
922 views

How to show $p_n$ $\leq$ $2^{2^n}$?

Let $p_n$ be the $n_{th}$ prime (e.g. $p_1 = 2$; $p_2 = 3$; $p_3 = 5$). Show that $p_n \leq 2^{2^n}$ for all $n$. I don't see how I can approximate the value of $p_n$. Do I need something like ...
2
votes
1answer
217 views

If a prime with prime norm is a split prime, in the number ring PID

If a prime with prime norm is a split prime , in an number ring PID? Example: $5-\sqrt{14}$ in $\mathbb{Z}[\sqrt{14}]$ has norm $11$, it is a split prime in $\mathbb{Z}[\sqrt{14}]$? Why? Thanks
3
votes
1answer
300 views

Prime congruence

If $p\equiv3\pmod{4}$ and $q=2p+1$ is a prime then $q|(2^p-1)$ if $2^p-1$ is composite. Also, prove that there are infinitely many primes $p$ for which $2^p-1$ is composite.
8
votes
1answer
506 views

The largest possible prime gap?

What is the largest possible prime gap if we observe only 1000-digits numbers? There are few conjectures about this question but is there something that we can say and be absolutely sure of it?
4
votes
2answers
274 views

What's wrong with my proof of infinitely many primes of the form $am+b$, $\gcd(a, b) = 1$

So the prof said in class that the proof of this is hard, but we might want to attempt at home. I won't be able to see him again until Wednesday, but I'm guessing there is some hole in my proof, since ...
4
votes
1answer
248 views

How to find primes between $p$ and $p^2$ where $p$ is arbitrary prime number?

What is the most efficient algorithm for finding prime numbers which belongs to the interval $(p,p^2)$ , where $p$ is some arbitrary prime number? I have heard for Sieve of Atkin but is there some ...
28
votes
3answers
573 views

Sequence of numbers with prime factorization $pq^2$

I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions: What is the ...
5
votes
3answers
449 views

Powers as a complete residue system modulo $p$?

Question 1. With $0 < a < p$, $p$ prime and $\gcd(a,p-1)=1$, is it true that $0, 1, 2^a, ...,(p-1)^a$ is a complete residue system modulo $p$? If not, will a similar statement hold? Question ...
5
votes
3answers
363 views

Properties of Fermat primes

Fermat primes 17 and 257 appear a lot in the prime composition of numbers of the form $a^{2^n}+1$. For example, $11^8+1$ is divisible by 17 and $11^{32}+1$ is divisible by 257. I have verified the ...
1
vote
0answers
97 views

Infinite number of primes in the sequence $1+t^2$? [duplicate]

Possible Duplicate: Primes of the form $n^2+1$ - hard? $1, 2, 5, 10, 17, \ldots$ Are there an infinite number of primes in this sequence $1 + t^2$, $t$ being an integer?
2
votes
5answers
1k views

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$
9
votes
2answers
211 views

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime?

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime? While answering @pedja's question about the existence of any such representations I was ...
6
votes
1answer
556 views

Are the primes found as a subset in this sequence $a_n$?

Below is a introduction that contains some background to my question. The question is found at the bottom. By calculating the eigenvalues of the matrix defined by the recurrence: $\displaystyle ...
3
votes
1answer
349 views

Even numbers greater than 10 as sum of two specific odd numbers

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved(or disproved) ,so my question is: Is it true that every even number ...
2
votes
1answer
755 views

Even numbers greater than 6 as sum of two specific primes

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved ,so my question is: Is it true that every even number greater than 6 ...