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
5answers
97 views

What is $\limsup_{n\to\infty} \frac{p_{n+1}}{p_n}$?

Let $(p_n)_{n\in\mathbb N}$ be the strictly increasing sequence of all primes. I'm wondering what $$S:=\limsup_{n\to\infty} \frac{p_{n+1}}{p_n}$$ is. Is the result already known? By Bertrand's ...
3
votes
2answers
70 views

Consecutive squarefree numbers of 5 prime factors each, mostly small

The sequence of numbers 49297533, 49297534, and 49297535 is notable, because the factorizations of these numbers are each of the form $a^1 \cdot b^1 \cdot c^1 \cdot d^1 \cdot e^1$, where $\{a\ldots ...
7
votes
1answer
147 views

Conjectured compositeness tests for $N=b^n \pm b \pm 1$

How to prove that these conjectures are true? Definition: 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)$, where $m$ and $x$ are nonnegative ...
0
votes
0answers
16 views

Is $p_n \sim \frac{5}{4}n\log(n) + \frac{1}{2}n + \frac{(p_1+\ldots+p_{n-1})}{n-1}$ a good approximation for the $n^\text{th}$ prime?

If you plot the following function $$f(n) = \left|\frac{(p_1+\ldots+p_{n})}{n} - \frac{(p_1+\ldots+p_{n-1})}{n-1}\right|$$ you get a graph that is similar to $$f(x) = \frac{5}{4}\log(x) + ...
1
vote
0answers
39 views

On n! divided by a product of primes and related questions

We have the following Definition 1. For integers $n\geq 1$ we define $$f(n) = \begin{cases} 1, & \text{if $n=1$} \\[2ex] \frac{n!}{\prod_{p\leq n}p}, & \text{if $n>1$} ...
6
votes
1answer
77 views

$\tau$ and grouping of prime numbers

From Prime Number Theorem and this we can state $$\frac{p_n}{\bar{p}}\sim 2$$ or $$\lim_{n\to \infty} \frac{np_n}{(p_1 + \dots +p_n)} = 2$$ If we then look at the fluctuations in the graph of $$f(n) ...
1
vote
1answer
34 views

Likelihood at least 2 out of $n$ numbers are visible to each other in $\mathbb{Z}^n$

Two points in $ \mathbb{Z}^n $ are said to be visible to each other, if they can be connected by a straight line, which doesn't intersect any points of $ \mathbb{Z}^n $ In Apostol's book "An ...
4
votes
2answers
143 views

The sum of the reciprocal of primeth primes

A few days ago, a friend of mine taught me that the sum of the reciprocal of primeth primes $$\frac{1}{3}+\frac{1}{5}+\frac{1}{11}+\frac{1}{17}+\frac{1}{31}+\cdots$$ converges. Does anyone know some ...
3
votes
1answer
215 views

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
2answers
57 views

Modular Arithmetic and prime numbers

With respect to the maths behind the Diffie Hellman Key exchange algorithm. Why does: (ga mod p)b mod p = gab mod p It might be fairly obvious, but what basic maths guarantees this? Why does the ...
2
votes
2answers
65 views

Prove that $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \pmod p$

I'm trying to prove the statement $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \mod p$ and I don't really know where to start. Obviously $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} = 2\sum_{t=1}^{(p-1)/2} ...
2
votes
4answers
57 views

If $S$ is the set of all numbers of the form $3k + 1$, prove that any number $a$ in the set is prime or product of primes.

$S = \{1, 4, 7, 10, \ldots \}$ $10$ and $25$ are prime with regard to the elements of $S$ but $16 = 4 \times 4$ and $28 = 7 \times 4$ are not. I have been stuck on this problem as I am not sure of ...
7
votes
1answer
30 views

Smallest witness for checking the primality of a number

In this link https://primes.utm.edu/prove/prove2_3.html it is stated that the smallest witness for a composite number is always less than $2ln(n)^2$ , assuming the extended Riemann-hypothesis. ...
1
vote
4answers
84 views

What makes the Mersenne primes formula more special than any of these formulas?

Mersenne Primes Formula $2^n-1$ gives false results just like any of those ones: $3^n-2, 4^n-3, P_1\cdot P_2+P_1+P_2$, or $5^n-4$ and so on.. I think that each of those formulas(including ...
8
votes
1answer
64 views

Primes of the form $x^2+n\cdot y^2$, given $n$?

In an attempt to get to grips with algebra for a course I intend to follow, I was working through a bunch of exercise sheets. A series of questions got me wondering: Given an integer $n$, is there ...
5
votes
1answer
37 views

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime.

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime. Though I didn't check the statement with so many integers, but it looks like the equation never ...
6
votes
3answers
208 views

Conjectured compositeness tests for $N=k \cdot 2^n \pm c$

How to prove that these conjectures are 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 ...
7
votes
3answers
227 views

Conjectured Primality Test for $N=8\cdot 3^n-1$

Definition 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)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=8\cdot 3^n-1$ ...
-3
votes
1answer
42 views

Find all natural numbers *a*, that satisfy the following: [on hold]

Find all natural numbers a for which $$ \frac{a^4+4}{17} $$ is prime.
1
vote
1answer
68 views

Proof concerning specific class of Proth numbers

Is this proof acceptable ? Theorem Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $k$ odd and $3 \nmid k $ , thus $N$ is prime iff $3^{\frac{N-1}{2}} \equiv -1 \pmod N$ Proof Necessity ...
7
votes
0answers
34 views

Does $S(n)$ contain infinite many primes? [duplicate]

Denote $p_j := j\text{th prime}$ and $S(n)\:=\sum_{j=1}^n p_j$ (The sum of the first $n$ primes). Is it known whether $S(n)$ is prime for infinite many $n$? OEIS gives the sum of the prime ...
0
votes
1answer
22 views

Euclid's Lemma using FToA

I would really appreciate some help understanding the following passage from my Real Analysis text. I have a professor who uses inquiry based learning, which basically means we all stare at each other ...
4
votes
3answers
105 views

Prove $\log_7 n$ is either an integer or irrational

I have been trying to prove a certain claim and have hit a wall. Here is the claim... Claim: If $n$ is a positive integer then $\log_{7}n$ is an integer or it is irrational Proof ...
4
votes
2answers
268 views

Formula for prime counting function

I saw this formula on this paper page 2 $$\pi (n)=\sum_{j=2}^{n}\frac{\sin^{2}\left(\pi \frac{(j-1)!^{2}}{j}\right)}{\sin^{2}(\frac{\pi }{j})}$$ Where $\pi(n)$ is the prime counting function. Is ...
2
votes
0answers
51 views

“Race” of the primes modulo $1,3,7,9\ \pmod {10}$

The "race" starts with the prime $11$. The number of primes $1, 3, 7, 9 \pmod {10}$ is denoted after every occurring prime. Does the lead change infinitely often? And does every "runner" have ...
-1
votes
1answer
40 views

How many ways can a quadratic form represent a prime?

Given $a,b,c,p\in\Bbb N$ with $b^2-4ac<0$ and $p$ is a prime with $\bigg(\frac{b^2-4ac}p\bigg)=1$, how many solutions $(x,y)\in\Bbb Z^2$ are there to $$ax^2+bxy+cy^2=p?$$
2
votes
0answers
38 views

Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ? Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$ ...
6
votes
2answers
67 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...
2
votes
2answers
47 views
3
votes
1answer
80 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 ...
5
votes
3answers
138 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 ...
5
votes
2answers
49 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, ...
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
1answer
30 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 } ...
5
votes
1answer
57 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 ...
0
votes
0answers
34 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 ...
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
28 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
74 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 ...
5
votes
2answers
307 views

The longest sequence of numbers with a certain divisibility property

Definition - Denizen A sequence $\lbrace a_k \rbrace$ is a denizen if all of it's members are prime numbers, i.e $a_0, a_1, ... a_n \in \mathbb{P} $; and it satisfies the following condition; ...
0
votes
2answers
100 views

How many prime numbers we need? [closed]

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 ...
13
votes
0answers
199 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
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 ...
3
votes
2answers
87 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 ...
0
votes
1answer
57 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 ...
2
votes
2answers
50 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 ...
2
votes
2answers
65 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 + ...
-3
votes
0answers
17 views

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

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
4answers
74 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?