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

1
vote
0answers
10 views

Is there a short proof of the existence of $a$ so that $a$ is a primitive root for infinitely many primes $p$?

After looking for a general answer I found Artins conjecture, and I was happy to see so much is known. However I don't know nearly enough to follow the proof, yet it bothers me I can't prove the ...
33
votes
7answers
2k views

$-1$ as the only negative prime.

I was recently thinking about prime numbers, and at the time I didn't know that they had to be greater than $1$. This got me thinking about negative prime numbers though, and I soon realized that, for ...
58
votes
5answers
7k views
1
vote
2answers
117 views

Show that if $p$ is an odd prime, show a power $p^k$ can never be a perfect number

Show that if $p$ is an odd prime, show a power $p^k$ can never be a perfect number. I am little confused about this problem, any insight?
5
votes
1answer
850 views

Super Perfect numbers

A super-perfect number is a number with $\sigma(\sigma (n))=2n$. How can I prove that every even super perfect number is from the form $n=2^k$ when $2^{k+1}-1$ is prime. I tried every way please ...
4
votes
2answers
624 views

Can powers of primes be perfect numbers?

I need to prove the following, though I'm not 100% certain I understand the definition of a perfect number. Prove that no perfect number is a power of a prime. First of all, I'm assuming that ...
-1
votes
0answers
32 views

Hypothetical proof of Goldbach's conjecture?

Goldbach's conjecture: Every even number greater than 4 is the sum of two prime numbers. An equivalent statement is; For all $n\geq 2$ there exists a number $e(n)$ such that $n-e(n)$ and ...
3
votes
2answers
56 views

Prime counting function; when is it true that $\pi(n) > \pi(2n) -\pi(n)$?

Let $\pi$ be the prime counting function. Under what conditions is it proven true that $\pi(n) > \pi(2n) -\pi(n)$, if at all?
0
votes
0answers
15 views

Is there a proof that $(n-2x)! \times n^{2x-1} > n!$ (where $x$ is a function related to the prime counting function

Is it possible to prove the following? Let $\pi$ be the prime counting function and $A(n)=\pi(2n)-\pi(n)$ $(n-2A(n))! \times n^{2A(n)-1} > n!$
2
votes
3answers
141 views

Explain the proof that the root of a prime number is an irrational number

Though the proof of this is done in a previous question, I have some doubt about a certain concept. So I ask to clarify it. In the proof we say that $\sqrt{p} = \frac{a}{b}$ (In their lowest ...
0
votes
2answers
37 views

How to check if a a relatively small number is prime (4 digits at most)?

I have an undergrad degree. Either I missed it or they didn't teach us, but how can I check (without using a computer) if a number, say 1033, is prime?
0
votes
0answers
14 views

Show that $s(x)=\pi(x)/x+\int_1^x \frac{\pi(t)}{t^2}\,dt$

For $x\in\mathbb{R}$, let $\pi(x)=\#\{$ primes $p:p\le x\}$ and let $s(x)=\sum\limits_{\text{primes}} \frac{1}{p}$. Given that: If $a_1, a_2, \dots \in \mathbb{R}$ and $f$ is a $C^1$ function in an ...
1
vote
2answers
32 views

Generalizing Legendre's Theorem on prime factorization of factorials

From Legendre's Theorem we know $$n!=\prod_{p}p^{\lceil \frac{n}{p}\rceil +\lceil \frac{n}{p^{2}}\rceil +.. }$$. Since $\Gamma (n+1)=n!$, i wonder if there is a generalization of this formula for ...
3
votes
2answers
78 views

Product of Primes

Let $\mathbb{P}$ denote the set of prime numbers. How would one evaluate $$\prod_{p\in \mathbb{P}}\frac{p-1}{p}$$ I do not think that the fact that ...
2
votes
2answers
31 views

Is there an alternative approach to the definition of prime numbers based on the definition of the natural logarithm?

Is there an alternative approach to the definition of prime numbers based on the definition of the natural logarithm? These are my thoughts about it, the questions are at the end: Basically when a ...
1
vote
1answer
44 views

How I can prove that for any natural number $n$ such that $30<n$, $\pi(4n-3)<n$?

I need to proove that for any natural number $n>30$: $$\pi(4n-3)<n.$$ In this inequality, $\pi(x):\mathbb{N}\to \mathbb{N}$ is the defined as follows: $$\pi(x):=Card(\lbrace p \ | \ p\leq x\ \ ...
10
votes
2answers
99 views

How was the 506-digit prime number 999…9998999…999 found?

I was surprised to encounter a claim made on the internet that the following number is prime: ...
3
votes
3answers
72 views

How can I prove that only there continuous odd prime are $3,5,7$?

How can I prove that the only prime number $p$, such that $ p,p+2,p+4$ are primes is 3?
1
vote
1answer
43 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
2
votes
3answers
73 views

For what numbers $n$ is $\sqrt{n}$ irrational?

I would say it has something to do with the numbers that can be expressed as a factor of different prime numbers, but when I get to $8$, that can be changed to $2^3$, which goes against this. Is there ...
0
votes
0answers
30 views

Is there an arbitrarily large set of naturals so that the sum of each two has exactly $n$ prime divisors? What about an infinite set? [on hold]

Is there an arbitrarily large set of naturals so that the sum of each $2$ has exactly $n$ prime divisors where $n$ is fixed? What about an infinite set? For $n=1$ this is clearly false, what ...
1
vote
2answers
65 views

How can Mersenne Prime rule be valid if $2047$ isn't prime?

The rule of Mersenne Prime says that $2^p - 1$ is prime if $p$ is prime. $2^{11} - 1 = 2047$ satisfies the condition, but it's not a prime as it can be divided by two prime numbers $23$ and $89$. ...
0
votes
2answers
25 views

Euler's proof of Infinitude of Primes: If a prime divides an integer, why would it have to divide 1?

Here's the Euler's proof of Infinitude of Primes in Rosen's Discrete Mathematics: We will prove this theorem using a proof by contradiction. We assume that there are only finitely many primes, ...
0
votes
0answers
22 views

Prime division algebra level 5

Let $P$ be the number of integers $n$  for which $n^4-52n^2+595$ is prime, and let $D$ be the number of distinct primes that can be represented in this form. Find $P+D$.
2
votes
0answers
19 views

Finite amount of consecutive smooth numbers

is there a short proof of the fact that there is a finite amount of consecutive smooth numbers (meaning Given a finite set B, there is a finite amount of pairs $n,n+1$ so that both can be expressed as ...
0
votes
0answers
17 views

What are some easy to prove results on the density of primes?

Bertrand's postulate states that for any integer $n>3$, there's always a prime $p$ between $n$ and $2n-2$. That result sets a reasonable 'lower bound' on how often we can expect primes to show up, ...
1
vote
3answers
65 views

At what rate are composites removed in a set after each prime multiple is cancelled out?

I was looking at sieves today, mainly sieving for primes and I noticed a pattern type thing. As I crossed out primes in a small set, the number of composites that were crossed out decreased. I haven't ...
1
vote
2answers
38 views

Prove that there exists infinitely many primes of Digital root $2,5$ or $8$

I am highly interested in properties of digital root. Digital Root: Digital root of a number is a digit obtained by adding digits of number till a single digit is obtained. It's clear that Digital ...
1
vote
1answer
31 views

How does the fact that Fermat primes are relatively prime imply there are infinite primes?

I was just reading a book called Proofs from the Book. It presented the proof given by George Polya to prove that two Fermat primes (numbers of the form $2^{2^n} + 1$) are always relatively prime, ...
-1
votes
2answers
56 views

Proof for whether or not a function will ever be non-prime.

From the proof that there are infinitely many primes: Given all the primes $p_i$ known up to the $n$th prime, construct the number $q_n$ such that $$ q_n = 1 + \prod^{n}_{i=1} p_i $$ Since there is ...
1
vote
0answers
64 views

A method of writing all primes

I've recently noticed a method of describing primes. As an example: $13=5*11-2*3*7$. This pattern must follow these rules: $x-y$ such that $x*y$ is the product of all previous primes (allowing powers ...
1
vote
0answers
16 views

Does there exist a $k$ such that for all $n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$?

Does there exist a $k \in \mathbb{R}$ such that for all $n \in \mathbb{N}, n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$, where $\text{gpf}(x)$ is the greatest prime factor of $x$? I ...
11
votes
1answer
89 views

Is there a polynomial such that $F(p)$ is always divisible by a prime greater than $p$?

Is there an integer-valued polynomial $F$ such that for all prime $p$, $F(p)$ is divisible by a prime greater than $p$? For example, $n^2+1$ doesn't work, since $7^2+1 = 2 \cdot 5^2$. I can see that ...
14
votes
1answer
160 views

Simple(r) proof that $\pi(2^n)\geq n$?

We can clearly prove that $\pi(2^n)\geq n$ with Bertrand's postulate, but that seems like overkill. Is there any simpler way one can prove that $\pi(2^n)\geq n$? Note: $\pi(m)$ is the prime ...
0
votes
1answer
40 views

Proving the primality of these large numbers?

In 2007, Vautier claimed that the largest known consecutive pair of prime numbers (at the time) was $2003663613\cdot2^{195000}-1$ and $2003663613\cdot2^{195000}+1$. I was wondering how Vautier found ...
2
votes
1answer
29 views

Complexity of generating a prime larger than $N$

Is it provably difficult to generate a prime larger than a prescribed $N$? For instance, if I want a prime of $1000$ digits, is there a way to do that deterministically, i.e., without resorting to AKS ...
11
votes
0answers
70 views

Consecutive prime numerators of harmonic numbers?

Let $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\frac{a}{b}$$ and let $a$ and $b$ are coprime, $h_{n}=a$. $h_{n}$ is prime for ...
7
votes
1answer
108 views

Is $k+p$ prime infinitely many times?

I have the following conjecture: Let $k\in\mathbb{N}$ be even. Now $k+p$ is prime for infinitely many primes $p$. I couldn't find anything on this topic, but I'm sure this has been thought of ...
9
votes
1answer
348 views

Interpolating the primorial $p_{n}\#$

The primorial $p_{n}\#$ is given by the product $p_n\# = \prod_{k=1}^n p_k$ (where $p_{k}$ is the $k$th prime) -- is there a natural (a la the gamma function $\Gamma(z)$) way of interpolating it for ...
0
votes
0answers
30 views

Find k-th element of the sequence

Please, help me with effective algorithm to: Find k-th element of the sequence {n | (6n-1), (6n+1), (12n+5) are primes} Find k-th element of the sequence {n | (6n-1), (6n+5), (12n-7) are primes}
2
votes
1answer
30 views

Sum of reciprocals of n-digit primes

I have observed, by calculation, that the sum of the reciprocals of all the n-digit prime numbers is approximately 1/n, and that this becomes increasingly accurate as n increases. Is there a simple ...
0
votes
2answers
2k views

Proof — Infinitely many primes of the form $4k + 3$ — origin of $4(p_1…p_k - 1) + 3$

I know there are sundry questions — like this pdf — and this (10.) Prove that any positive integer of the form $4k + 3$ must have a prime factor of the same form. Because $4k + 3 = 2(2k + 1) + 1$, ...
0
votes
1answer
41 views

What is the simplest way to show that ${(p-1)! \over (k)!(p-k)!}$ is an integer?

In the proof of $p$ | $\binom{p}{k}$ (p divides $\binom{p}{k}$) where $p$ is prime, what is the simplest way to show that $${(p-1)! \over (k)!(p-k)!}$$ is an integer?
0
votes
1answer
19 views

The form of solutions of $p*k-q*j=r,$ for $(p,q)=1$.

I would like to find the form of solutions of $p*k-q*j=r,$ for $(p,q)=1$ for any fixed $r < pq$ and $k,j \in \mathbb{N}$. I tried to look at the divisibility of $p=cq+b.$ But I didn't have any ...
-10
votes
0answers
95 views

Is the Riemann Hypothesis incorrect? [closed]

See the attached image I would like to know your opinion about if the zeros shown in this picture can be considered as the zeros mentioned by Riemann in his Z function. I think yes and that his ...
4
votes
1answer
41 views

Aren't Legendre's conjecture and Andrica's conjecture same?

If Legendre's conjecture is true, couldn't we easily obtain $\sqrt{p_{n+1}}-\sqrt{p_{n}}<1$ where $p_{n}$ is the $n$th prime? $$p_{n+1}<(\lfloor \sqrt{p_{n}} \rfloor + 1)^{2}<( \sqrt{p_{n}}+ ...
5
votes
2answers
123 views

In what quadratic or quartic integer ring is a prime of the form $a^4 + 4^b$ guaranteed to split?

The obvious choice seemed at first to be $\mathbb{Z}[\root 4 \of 4]$. But since I know next to nothing about quartic fields, I thought to look in the quadratics. For the first few such primes in ...
1
vote
2answers
83 views

Using binomial theorem to prove $a | b^n \Rightarrow a | b$. ( | is divides, a prime, n integer > 1)

I tried expanding $(b-a+a)^n=$[$(b-a)+a$]$^n$ but it just seemed to further complicate the problem. I also tried to prove the contrapositive but that doesn't seem to lead to anywhere to. Is there any ...
2
votes
1answer
39 views

Prove the “Chebyshev's theorem”

I know the Chebyshev's theorem for primes that is : Theres a p between n,2n if n>1 Can you prove it easily? Actually im just 13 years old and I couldn't found an answer that I can understand it ...
1
vote
2answers
39 views

If $p$ is a prime other than 2 or 5, prove that $p$ must be one of the forms $10k + 1$, $10k + 3$, $10k + 7$, or $10k + 9$

If $p$ is a prime other than 2 or 5, prove that $p$ must be one of the forms $10k + 1$, $10k + 3$, $10k + 7$, or $10k + 9$ -The section we are covering is on the division algorithm, although I am ...