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
0answers
17 views

Trying to understand a step in Ramanujan's Proof of Bertrand's Postulate regarding the gamma function

My question relates to this step in the proof here: But it is easy to see that $$\log \Gamma(x)-2\log\Gamma(\frac12x+\frac12) \le \log\left\lfloor ...
1
vote
0answers
16 views

Asymptotic expression for $3$ term arithmetic progression in the primes

I have found an asymptotic for the following sum using the circle method: \begin{align} R(n)=\sum_{\substack{p_1,p_2,p_3 \le n \\p_1+p_2=2p_3 }} \log (p_1) \log (p_2) \log ...
5
votes
0answers
54 views

Which prime gaps are known to exist

It is easily proved that prime gaps can be arbitrarily large by constructing the sequence of composites $(n+1)! + 2, (n+1)! + 3, \dots, (n+1)! + (n+1)$, which are divisible by $2, \dots, n+1$ ...
1
vote
2answers
28 views

How to recognise the digit multiplication, subtraction or addition when checking for divisibility by 7, 11, 13, 17 and 19?

I was studying this page Divisibility by prime numbers under 50 to check for the divisibility by 7, 11, 13, 17, 19 etc. Is there any way to recognise whether to add or sub the given times of unit ...
1
vote
0answers
34 views

Do you know any answer for equation y^2 = x^3 + k? [duplicate]

As you know, the equation y^2 = x^3 + k for k like (4n-1)^3 - 4m^2 that m , n are integers & no prime number that p is congruent to 1 modulo 4 count m, don't have any answer & it's proof is by ...
2
votes
3answers
40 views

Prove that for any natural number $n$ there exists a prime number $p$ greater than $n$

Prove that for any natural number n there exists a natural prime number p , such that $ p>n $. How can I prove that ? Thank you.
13
votes
1answer
246 views

Numbers that are divisible by the number of primes smaller than them

Let $\pi(n)$ denote the number of primes less than or equal to $n$ (a.k.a the prime-counting function). For certain values of $n$, the value of $\frac{n}{\pi(n)}$ is integer. Here are the first few ...
5
votes
1answer
72 views

Paul Erdős showed a simple estimate for $\pi(x) \ge \frac{1}{2}\log_2 x$; is it possible to tweak his argument to improve the estimate?

Paul Erdős gave a simple argument to show that $\pi(x) \ge \dfrac{1}{2}\log_2 x$. Is it possible to tweak the argument and get a better estimate? I am wondering how good an estimate for $\pi(x)$ can ...
1
vote
0answers
48 views

The sum of consecutive odd primes has at least three prime factors, not necessarily distinct [on hold]

Given the odd primes $3, 5, 7, 11, 13, 17, 19,\ldots, 2n-1$, prove that if $p$ and $q$ are adjacent odd primes in this list, then $p + q$ necessarily has $3$ prime factors. We do not require the ...
1
vote
3answers
51 views

Infinitely many primes of the form $6n - 1$

Prove there are infinitely many primes of the form $6n - 1$ with the following: (i) Prove that the product of two numbers of the form $6n + 1$ is also of that form. That is, show that $(6j + 1)(6k + ...
1
vote
0answers
25 views

Solutions $n^2 = -1 \mod (p_n-1)$

Consider the equation $n^2 = -1 \mod (p_n-1)(*)$ where $p_n > n$ and $f(n) = p_n$ is the largest prime that satisfies the equation. $f(n)$ gives $p_n$ assuming there is a solution to the equation ...
4
votes
3answers
157 views

What is so great about 7?

I'm going to write down my problem verbatim: Write down the integers from $1$ to $50$ in rows of $10$ numbers each. Mark out $1$, and then cross out all multiples of $2$ greater than $2$ ...
0
votes
0answers
22 views

Fermat Prime Numbers Coprime [duplicate]

Fermat numbers are shown by: $F_m = 2^{2^m} + 1$. How can I prove that for any $m ≠ n$, I can have $(F_m, F_n) = 1$, or coprime?
0
votes
1answer
25 views

Infinite Prime Numbers: With Fermat Numbers

Suppose that the Fermat numbers $F_m$ are pairwise relatively prime. Can someone help me prove, given this, that there are infinitely many primes.
0
votes
1answer
25 views

Proving a statement similar to the Fermat's theorem using modular arithmetic.

I have to prove that if m > 1 and not a prime, then $\exists a,b,c \in \mathbb{Z}$ such that $c \not= 0 (\mod m)$, $ac = bc (\mod m)$, but $a \not = b (\mod m)$. I am sorry I don't know how to put ...
1
vote
3answers
50 views

Proof of non divisibililty of $\binom{n}{r}$ with a prime $p$

I came across this : "It is possible to show that if $p$ is prime, $\binom{n}{r}$ is not divisible by $p$ if and only if the addition $r + (n-r)$, when written in base $p$, has no carries. This means ...
1
vote
1answer
34 views

A theory of radicals of integers?

It seems to me that radicals, natural numbers without power factors, generalize the concept of primes. You could ask after the nth radical and the number of radicals less than a specified number. But ...
4
votes
1answer
121 views

Question about Paul Erdős’ proof on the infinitude of primes

I was reading Julian Havil’s book Gamma where he talks about a short proof by Paul Erdős on the infinitude of primes. As I understand it, here are the steps: (1) Let $N$ be any positive integer and ...
3
votes
5answers
55 views

Manually obtainining a list of primes $\leq n$, by using the root of n?

In my abstract math class I learned that if we want to get a list of primes $\leq n$ manually, we have to calculate the root of n, and the floor of that result will be the greatest number for which to ...
1
vote
1answer
25 views

Series involving primes

Trying to find an asymptotic bound for the series $$ S(x) =\sum_{p\leq x}\frac{\varphi(p-1)}{(p-1)p} $$ as $x \rightarrow \infty$. Of course $$ \frac{\varphi(p-1)}{p-1} =\prod_{q\mid ...
2
votes
1answer
24 views

sucessive primes with distance greater than k

I am studying bounds in prime gaps and I would like to gather as much information as I could. I am just an undergraduate student, it's not a very important project, I am just doing it by curiosity. I ...
7
votes
2answers
302 views

Consecutive numbers that share the same sum of prime factors

Let $f(n)$ denote the sum of the prime factors of $n$ (with multiplicity). I have been looking for pairs of consecutive numbers $n,n+1$ such that $f(n)=f(n+1)$. Case #$1$: ...
0
votes
2answers
32 views

Prove if $ord_p(d) < ord_p(n)$ then d divides n

I have to prove that $d$ divides $n$ if and only if $ord_p(d)\leq ord_p(n)$ I have already proved that $ord_p(d)\leq ord_p(n)$ if $d$ divides $n$ but I am struggling to prove the converse. Can ...
1
vote
4answers
131 views

Proving that $p_1p_2\mid n$ iff $p_1\mid n$ and $ p_2\mid n.$

Let $p_1$, $p_2$ be distinct primes. Using the Fundamental Theorem of Arithmetic prove that a natural number $n$ is divisible by $p_1p_2$ if and only if $n$ is divisible by $p_1$ and $n$ is divisible ...
0
votes
1answer
38 views

On no. of solutions of product of positive integers equal to sum

$n \ge 2$ be an integer , let $a(n)$ be the no. of solutions in positive integers of $x_1+x_2+...+x_n=x_1x_2...x_n ; x_1 \le x_2 \le ... \le x_n$ , then is it true that $a(n+1)=1 \implies n$ is ...
6
votes
3answers
101 views

Elementary proofs of prime gap theorems?

"Obviously" it is thrue that $p_{n+1}<2p_n$. Testing for $n<10$ shows it is true for small $n$ and no mathematician or wannabe has ever doubt that it is true for big $n$. But there is no real ...
1
vote
1answer
73 views

How did Gauss discover the prime number theorem?

Carl Friedrich Gauss conjectured in his early youth that $$\lim_{x \rightarrow \infty} \frac{\pi(x)}{x/\log(x)} = 1.$$ Any idea how did he reach such result?
-1
votes
1answer
168 views

Proof for Goldbach's Conjecture [closed]

There is a proof given here. I couldn't find any flaw in it, what's wrong with it?
6
votes
0answers
66 views

Applying iterated function on the sum of the squares of the prime factors of $30$

Let $f(n)$ denote the sum of the squares of the prime factors of $n$ with multiplicity. For example, $f(60)=f(2\cdot2\cdot3\cdot5)=2^2+2^2+3^2+5^2=42$. Denote the iterated function ...
0
votes
0answers
33 views

Divisibility of a power sum by a prime

For a given prime $p>2$ and positive integer $k$, let $$S_k=1^k+2^k+...+(p-1)^k$$ We have to find the values of $k$ for which $p|S_k$. By the binomial theorem we know that $p|i^k+(p-i)^k$ when $k$ ...
2
votes
0answers
78 views

$f(x)\sim 1/x \implies (1+f(x))^x\to e$, but what family of functions maximizes the speed of convergence from below?

This problem is subordinate to finding out if $$\left(1+\frac{\log p_{n+1}}{p_n}\right)^{p_{n+1}/\log p_n},$$where $p_n$ is the $n$-th prime, never stabilizes above or below its limiting value, which ...
3
votes
3answers
37 views

Find all the positive integers $m$ such that $p_{m}≥2m$

Find all the positive integers $m$ such that $$p_{m}≥2m$$ where $(p_{m})$ is the sequence of prime numbers I have no idea to start.
3
votes
2answers
120 views
+50

A natural number $n>2$ is a prime iff $\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}$

Is this proof acceptable ? Theorem 1 (Wilson). A natural number $n>1$ is a prime iff: $$(n-1)! \equiv -1 \pmod n.$$ Theorem 2. A natural number $n>2$ is a prime iff: ...
1
vote
1answer
27 views

Need help with notation — finite set of random primes

I need help with notation for a finite set of random primes. Edit I've inserted my take on the format from the answer. Does it work? My attempt:$$\{X\in\binom{\mathbf P_{3,100}}{20}\},$$ ...
0
votes
1answer
32 views

are there infinitely many primes in Fibonacci sequence

There is one proof about infinitude of prime with following method, http://www.ams.org/mathscinet-getitem?mr=2271540 Also it is well know that any two consecutive Fibonacci numbers are mutually ...
0
votes
1answer
27 views

Prime dividing multinomial [closed]

Let $p$ be a prime. I was wondering for what numbers $a_1,\ldots,a_p$ such that $a_1 + \ldots + a_p = p$ that $p\mid\binom{p}{a_1,\ldots,a_p}$?
-2
votes
0answers
81 views

Erdos' proof that there are infinitely many primes [closed]

I don't fully understand Erdos' proof that there are infinitely many primes (pages 7-8 of this). Could you write it out in some more details?
1
vote
1answer
72 views

If $a_n$ is prime then $n$ is prime too

Given sequence $(a_n)$ : $a_1=1, a_2=4, a_3=15, a_n=15a_{n-2}-4a_{n-3}$. Prove that if $a_n$ is prime then $n$ is prime too. It is easy to prove that $a_n=4a_{n-1}-a_{n-2}$ and ...
0
votes
0answers
36 views

Fermat Numbers are pairwise coprime $\implies$ infinitely many primes

Given that the Fermat numbers $F_m$ are pairwise relatively prime. Prove that there are infinitely many primes.
0
votes
4answers
102 views

Prove that there are infinite prime numbers of the form $6n-1$ [closed]

Can someone help me prove that there are infinitely many primes of the form $6n − 1$.
3
votes
3answers
114 views

Can anyone sketch the proof or provide a link that there is always a prime between $n^3$ and $(n+1)^3$

In a recent forum discussion on number theory, it was mentioned that A. E. Ingham had proven that there is always a prime between $n^3$ and $(n+1)^3$. Does anyone know if there is a link available on ...
2
votes
1answer
91 views

Solutions to $y^2 = x^3 + k$?

As you know, the equation $y^2 = x^3 + k$ for $k = (4n-1)^3 - 4m^2$, with $m, n \in \mathbb{N}$ and no prime number that p is congruent to 1 modulo 4 count m, don't have any answer and its proof can ...
12
votes
1answer
116 views

Are there infinitely many pairs of primes where one divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
3
votes
0answers
107 views

What is the value of $\sum_{p\le x} 1/p^2$?

My question is, what is the value of $$\sum_{p\le x} \frac{1}{p^2}?$$ More generally, what is the value of $$\sum_{p\le x} \frac{1}{p^n}?$$ How can we find it? For $\sum_{p\le x} 1/p$ the idea was ...
5
votes
0answers
113 views

Primes as sum of squares.

If $p_{i}$ and $p_{j}$ are two primes of the form $4k+1$ , with $p_{j} > p_{i}$, show that if $p_{j} \neq$ sum of two squares $p_{i}$ is also not equal to sum of two squares. It is well ...
11
votes
1answer
150 views

Is $\sum\frac1{p^{1+ 1/p}}$ divergent?

Is $\displaystyle\sum\frac1{p^{1+ 1/p}}$ divergent? How can we prove that it is divergent or convergent in analytic number theory? I know what bound of the n-th prime number is, and that its order is ...
1
vote
0answers
37 views

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation?

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation? $2$ is the only prime with $1$ one, the Fermat ...
3
votes
2answers
61 views

Cubes differences and primality

In an exercise (Project Euler 131, not to mention it), we are looking for perfect cubes of the form $n^3 + n^2 p$, where p is prime. I finally got the answer by trial and error but I don't understand ...
1
vote
4answers
87 views

Could someone be so kind as to explain this little summation to me?

So basically, the wording in this question, to me, is weird. It goes as follows: Explain why the following formula gives the power $e$ of a given prime $p$ in $n!$: $$e = ...
0
votes
0answers
14 views

Density of primes in a polynomial

Consider that p(x) is a polynomial with integer coeficients. What is the natural density of the below set? $$\{n\ |\ p(n)\ is\ prime\}$$ For example the density for $p(x)=x$ is zero and maybe in ...