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

2
votes
1answer
58 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 ...
1
vote
0answers
33 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$} ...
3
votes
5answers
81 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 ...
6
votes
1answer
76 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
142 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
64 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
29 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
207 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
225 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.
0
votes
1answer
64 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
137 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?
5
votes
0answers
50 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 ...
4
votes
1answer
57 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 ...