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

0
votes
1answer
7 views

Is every positive integer relatively prime to 1?

Because gcd(k,1)=1 where k > 0 is an integer.
2
votes
2answers
39 views

Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm.

Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm. Hint: why can't $p = 5$ or 7? So I have done the two hints and in both cases I get a 9 in my set of numbers, ...
3
votes
1answer
30 views

Does every prime of the form $4k+1$ divide a number of the form $4^n+1$?

While playing around with Fermat's little theorem I was asking myself the question in the title and I can't answer it...
0
votes
1answer
26 views

Can Stirling's approximation be used to obtain lower and upper bound for $\pi(x)$?

The Willan's formula is given as follows (taken from Ribenboim's Little book of bigger primes): $$ \pi(x)=\sum_{j=2}^{x}f(j) \text{ where } ...
0
votes
0answers
33 views

Trial division formula [on hold]

I'm not very good with mathematic notation, I'm trying to describe a formula for trial division. Can anyone point me in the right direction or provide an answer? Also please do explain the notation ...
5
votes
1answer
51 views

Proving that and how $ \frac{1}{n}\sum\limits_{p\le n}\lfloor n/p \rfloor - \sum\limits_{p\le n} 1/p $ approaches $0$

Let $p$ denote a generic prime number. By Mertens' second theorem, the sequence $$\sum\limits_{\ p \le n} \frac1p - \log\log n$$ converges to the Meissel-Mertens constant $M\approx 0.2614972$. Now let ...
5
votes
3answers
133 views

What's the smallest known interval containing at least one prime number?

Wikipedia says that Dusart proved in 2010 that there's at least one prime between $x$ and $\left(1 + \frac{1}{25\ln^2x}\right)x$ for $x \geq 396738$. For $x_0 = 396738$, this implies a prime between ...
3
votes
1answer
67 views

Which constellations of primes recur forever?

Having derived much joy and learning from the answers I have received to four previous questions, let me ask one more. Let a constellation of primes be a set of primes that stand in certain fixed ...
0
votes
0answers
15 views

Primes and even numbers [duplicate]

Can every even number be written up as the difference of two primes? And in either case could you prove it? $$ e.g.\space 8 = 31-23 \space and \space 10 = 41-31$$
1
vote
0answers
27 views

Ways Of Finding Primes and If they are efficient

I am currently in middle school and love number theory. I try and do a proof every day and today I was working on a relatively simple one involving primes. I proved that every prime above 5 can be ...
2
votes
1answer
71 views

Why is $p_n \sim n\ln(n)$?

I know that the prime number theorem states that the number of primes less than $x$ is approximately $\frac{x}{\ln(x)}$. However, why does this mean that $p_n \sim n\ln(n)$? (where $p_n$ is the $n$-th ...
0
votes
1answer
31 views

Lower bound for $\Pi(n)$ - viability of probabilistic theory

Can somebody check the validity of my arguments below, and tell me why its wrong or right? Consider the sequence of non-negative integers. Let $a_0=0, a_1=1, ..., a_i=i,...$ Divisiblilty of $a_i$ ...
0
votes
0answers
18 views

The distribution of prime and semi-prime.

Let $\alpha$ be an integer and $\rho_1,\rho_2$ some prime such that $\alpha=\rho_1\cdot\rho_2+1$, and $\beta$ the number of all semi-prime less than or equal to $\alpha$. Prove ...
0
votes
2answers
97 views

How many prime numbers we need? [on hold]

If we have some not prime number $n > 1$ we always can make prime factorization. For this operation we need $m$ prime numbers. Is there any way to prove that for given $n$ we can use no more then ...
2
votes
2answers
49 views

Is the sequence $\{0,2,6,12,20,30,…,n(n+1)\}$ admissible for every natural $n$?

Look here : https://en.wikipedia.org/wiki/Prime_k-tuple for the definition of an admissible sequence. I wonder if the sequence of differences of primes can be $\{0,2,4,6,8,...,2n\}$ for every ...
1
vote
1answer
25 views

Dirichlet theorem

Can anyone give a simple number theory proof for the Dirichlet theorem? Statement of Dirichlet theorem:given any two numbers a and b whose g.c.d is 1,Prove that infinitely many primes exist in the ...
-3
votes
0answers
17 views

what is formula to this eqution [(256)16]1/32+[(169)6]1/12 [on hold]

how to solve this equation [(256)16]1/32+[(169)6]1/12 what is formula of this? What is the closed form expression for this? What is the right domain for this Hamiltonian 2? what is the right ...
4
votes
1answer
55 views

Is every sufficiently large even integer the sum of distinct primes?

Is every sufficiently large even integer the sum of (any number of) distinct primes? No doubt this question has been asked before; does the conjecture/theorem have a name? It is related to ...
1
vote
1answer
54 views

Smallest twin-prime-pair exceeding $10^{1000}$

I found the twin-prime-pair $$\large 10^{1000}+9705092\pm 1$$ with PARI/GP. Is this the smallest twin-prime above $10^{1000}$ ? A general question to the search of twin primes : The prime number ...
2
votes
2answers
64 views

How do I find(isolate) the n-th prime number?

So I wanted to solve this SPOJ problem and I did some research about finding the n-th prime number. This formula came across and it stated that the n-th prime must be in this range: $n \ln n + ...
5
votes
0answers
43 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
1
vote
0answers
26 views

Is there a tighter approximation for the least prime gap of a given length?

This link https://primes.utm.edu/notes/gaps.html gives a definition of the maximal gaps. For a number $g$ , $p(g)$ is the smallest prime $p$ followed by at least $g$ composites. The estimate is ...
0
votes
0answers
23 views

Chebyshev's original proof of Bertrand's postulate

I'm looking for the original Chebyshev's proof of Bertrand's postulate. It would be great if someone could provide me the link to the article. Thank you in advance,
4
votes
4answers
71 views

Books on Prime numbers

I am a graduate student and have just finished Burton's book on number theory. Now I want to read further on prime numbers. Does anyone have any suggestion?
1
vote
1answer
35 views

For every natural integer $N>3$ there are at least two distinct prime numbers $p$ and $q$ such that $\dfrac{p+q}{2}=N$ and $N-p=q-N$, $(p<q)$.

I'm not sure but this problem may be similar or related to Goldbach conjecture? Any proof/disproof, insight and opinion is appreciated, thanks.
-1
votes
1answer
28 views

Is there a number which describes the approaching ratio of twin primes to other primes? Or a formula for the change in density of twin primes?

Could someone shed some light on what we know about the density of twin primes? I find that it seems to be empirically true that the density of prime gaps increases as $\log(x)$ does for any gap. ...
1
vote
1answer
18 views

Large pairwise coprime sets

Say that a set $S\subseteq\Bbb N$ is pairwise coprime if every two elements of $S$ are relatively prime. Denote by $f(n)$ the size of a maximal pairwise coprime subset of $\{1,...,n\}$. What is ...
3
votes
2answers
85 views

New deterministic primality test for numbers of the form $p\cdot 2^n + 1$

Edit: Sorry, there was an error. Old Claim (not true because there is a counter-example): Let $p$ be prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N = p\cdot 2^n+1$ is prime, if and only ...
3
votes
0answers
24 views

Kronecker symbol vs. Koblitz symbol

In Koblitz, Introduction to Elliptic Curves and Modular Forms on page 188 it is defined $$\left( \frac{-1}{j}\right)=0$$ in case $j$ is even. Apart from that definition $\left( \frac{c}{d}\right)$ is ...
0
votes
0answers
36 views

Why does $\frac{x^n}{n^x}$ stop growing at the approximate value of $\pi (n)$?

I noticed while playing around with these functions that $n^x$ will start slow and then speed up really fast in its growth rate. While $x^n$ grows more slowly, but faster than $n^x$ at the start. ...
1
vote
0answers
43 views

Does anyone recognize this graph?

It's a plot of the following: Let $$f_{(n)} = \frac{np_n}{(p_1 + \ldots + p_n)}$$ so that $$g_{(n)} = \left|\space f_{(n)} - f_{(n-k)}\right| $$ where $n > k$ and $k = 5$ in this example. For ...
0
votes
1answer
45 views

Show that there exists $s, t \in S$ such that $\gcd(s, t)$ is a prime

Let $S$ be a set containing finitely many positive integers greater than 1 with property: for all $n \in \mathbb{Z_+}$, there exist $s \in S$ such that $\gcd(s, n) = 1$ or $\gcd(s,n) = s$. Show that ...
1
vote
1answer
35 views

Why hash table size is prime? [closed]

In computer science, the size of the hash table is recommended to be prime. What is the property of prime number that makes it recommended to be the size of hashtable?
-3
votes
0answers
44 views

If $p$, $q$, and $r$ are all odd primes, which of $p^2-q^2+1$, $pqr+3$, and $(p+2)(r+2)+1$ can be prime? [closed]

If $p$, $q$, and $r$ are all odd primes, which of the following might also be a prime? a) $p^2-q^2+1$ b) $pqr+3$ c) $(p+2)(r+2)+1$
0
votes
2answers
61 views

Proof that every positive integer has at most one prime factor greater than it's square root?

I read the statement in the title somewhere but I can't find any proof. For a positive integer $n$, why can't there be 4 numbers $a, b, c, d$ ($b$ and $d$ are prime) for which $a < \sqrt{n} < ...
2
votes
0answers
35 views

Legendre symbol identity

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
-1
votes
1answer
59 views

Prove that $n^m+x$ is not prime generally if $n+x$ is (in $\Bbb N$)

If $n + x$ with $n, x \in \Bbb N$ is prime, is it possible to prove generally, that $n^m + x$ with $n, x, m \in \Bbb N$ is not prime for at least one $m$? If yes, how can this be done? EDIT: There ...
5
votes
2answers
74 views

Proving the irrationality of the concatenation of the $n$th powers of primes

Note: The apostrophes are meant to separate different groups of digits. Like, $0.{1^2}'{2^2}'{3^2}'{4^2}'\cdots=0.14916\cdots$. I wasn't able to come up with something better. It is easy to show ...
2
votes
0answers
128 views
+50

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ...
1
vote
3answers
37 views

Product of first $n$-th prime power integers $+ 1$

I was just playing with prime numbers and then I accidentally found this pattern. Let $p_1\cdot p_2\cdot p_3\cdots p_n$ is the product of first $n$-th prime power integers. Prove that: $p_1\cdot ...
2
votes
1answer
55 views

Besides 1 and 11, is $\sum_{i=0}^n 10^i$ composite for every $n\in \mathbb{N}$?

Given a number consisting of digits all equal to 1 in base 10 and not equal to 1 or 11, is it necessarily composite? I know that 11 is the smallest non-trivial counter-example, but I would like to ...
2
votes
1answer
63 views

Primes that are approximately twice other primes

Are there infinitely many pairs of primes of the form $p,2p-1$? What about $p,2p+1$?
6
votes
2answers
193 views

What is the smallest prime $p$ such that the next prime is greater than $p+2000\ $?

I studied this site https://en.wikipedia.org/wiki/Prime_gap and wondered if the smallest prime gap greater than $2000$ can still be determined, in other words : Which is the smallest prime $p$, ...
1
vote
0answers
30 views

Equivalent conjecture to Goldbach's conjecture

I'm reading a paper regrading the basis orders. In that paper, I met with the following statement: $$3(\mathbb{P}\cup\{0 \})=\mathbb{Z}_{\geq 2}$$, Which, by definition, states that primes form ...
1
vote
3answers
47 views

Fermat primality test $\gcd$ condition and carmichael numbers

Consider the following quote (I read similar thing in a couple of sources but this one illustrates the issue I'm having): By Fermat's Theorem if $n$ is prime, then for any $a$ we have $a^{n-1} = 1 ...
3
votes
0answers
84 views

What is the least prime $p$, such that $[p-1000,p+1000]$ does not contain a prime $\ne p$?

I am looking for the least prime number $p$, such that the interval $[p-1000,p+1000]$ contains no prime except $p$. In other words, the prime nearest to $p$ has a distance $>1000$ to $p$. I found ...
1
vote
1answer
43 views

Lunchroom Question: primes adding up to counting numbers?

Our lunchtime group got into another math related discussion. I apologize in advance if this isn't a rigorous question, as none of us are professional mathematicians. This is the question: Is it ...
0
votes
1answer
20 views

What's the condition for (x+kp) and pq being coprime?

Suppose $p$ and $q$ are large primes and $N=pq$. $x$ is an arbitrary integer in $\mathbb{Z}_p$ and $k$ is a random integer. Then what is the condition for $k$ (suppose $x$ is fixed) such that ...
0
votes
1answer
72 views

Is an algorithm to find all primes up to $n$ that runs in $O(n)$ time fast?

I kindly ask you if it is useful or fast for a prime number generator to run in $O(n/3)$ time? I believe I have a way to generate all $P$ primes up to $n$, quickly and neatly, in $P$ comparisons and ...
5
votes
1answer
95 views

Is $\lim_{n\to \infty} \frac{np_n}{\sum_{i=1}^n p_i} = 2$ true?

Noob here. I was playing around with primes in JavaScript and I found that if I divide the nth prime times n to the sum of primes up to n, I get closer to 2 for each n going to infinity: $$\lim_{n\to ...