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
109 views

Is there an obvious reason why $4^n+n^4$ cannot be prime for $n\ge 2$? [duplicate]

I searched a prime of the form $4^n+n^4$ with $n\ge 2$ and did not find one with $n\le 12\ 000$. If $n$ is even, then $4^n+n^4$ is even, so it cannot be prime. If $n$ is odd and not divisible by ...
1
vote
1answer
35 views

For how many integers is this a prime number?

For how many integers $n$ is: $9 - (n-2)^2$ a prime number? I want to try this using a rigorous definition of prime number/ actual problem rather than try-error? Please only give hints, so I can do ...
1
vote
0answers
29 views

Determine whether permutation of the digits of a number is prime

Given a number $m$ in decimal representation. I want to find a permutation of the digits of $m$, so it is prime. (Or output that there exists none) Do i have in the worst case check every possible ...
1
vote
1answer
19 views

Asymptotic formula for sums related to primes

Suppose $0 < \alpha < 1$. What is the asymptotic formula for the sum $$\displaystyle \sum_{p \leq x} \frac{\log p}{p^\alpha}?$$ Thanks for any insights.
0
votes
2answers
38 views

Sum of certain two-digit primes with prime digits

Let $P$ be a two-digit prime number less than $100$ such that both digits are prime numbers. What is the sum of all such numbers, $P$? Is there a quick way to solve this problem without listing all ...
2
votes
1answer
25 views

Origin of period function model of primes

There is a web page attributed to Omar Pol, "Sobre el patrón de los números primos: Determinación geométrica de los números primos y perfectos." ("On the pattern of primes: Geometric Determination of ...
0
votes
0answers
15 views

Understanding how to estimate $\pi(x)$ based on Paul Erdos's proof of Bertrand's Postulate

I am reading the 4th Edition of Proofs from the Book. I am not clear on how the proof behind Bertrand's postulate leads to the following statement on page 10 (of my edition): From (2) one can ...
3
votes
1answer
38 views

Prove for any integer $N$ that there exists $n > N$ where $n!-1$ is not a prime

I was thinking about Euclid's proof of the infinitude of primes and the fact that we could make the argument about $n!-1$ instead of $n!+1$ when I wondered if it would be easy to prove that for any ...
3
votes
1answer
77 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
24 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
62 views

Which prime gaps are known to exist [duplicate]

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
30 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
36 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
42 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.
14
votes
2answers
277 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
75 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
52 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
54 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
28 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
162 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
28 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 ...
2
votes
3answers
55 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
122 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
57 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
26 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
304 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
47 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
136 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 ...
-1
votes
1answer
48 views

On no. of solutions of product of positive integers equal to sum [on hold]

$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
104 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
177 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
69 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
36 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
81 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
38 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
152 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
30 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
33 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
29 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}$?
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.
3
votes
2answers
116 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
96 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
108 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 ...