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

$2^k+3$ : Primality Brute Forcing Theory Below The Square Root

I'm testing a theory of brute forcing $2^k+3$. I've tried to test $(2^k)+3$ where $k=84$ but my computer just takes too long... Java takes too long too.. It's pretty stupid to assume 83 tests makes ...
4
votes
3answers
536 views

Prove that 10101…10101 is NOT a prime.

So basically we have a number $10101...10101$ that contains $2016$ zeros and can be written as$ \sum _{ k=0 }^{ 2016 }{ 100^{ k } }$ . I want to prove that this number is not a prime without using ...
0
votes
0answers
12 views

Is always two times an even semiprime at a distance $1$ or prime to the closest previous odd semiprime?

This is an observation regarding the semiprimes, also named 2-almost primes, biprimes, or the product of two primes. This week I do not have a computer, only a tablet (hospitalized with a lot of free ...
2
votes
0answers
27 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 ...
0
votes
0answers
40 views

Hypothetical proof of Goldbach's conjecture? [on hold]

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 ...
0
votes
0answers
19 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!$
4
votes
2answers
62 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
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 ...
2
votes
2answers
34 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 ...
2
votes
2answers
33 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
47 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\ \ ...
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 ...
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 ...
3
votes
3answers
74 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 ...
11
votes
2answers
101 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: ...
36
votes
8answers
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 ...
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
66 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
23 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
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
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 ...
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
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 ...
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 ...
11
votes
1answer
90 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 ...
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
71 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 ...
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 ...
7
votes
1answer
109 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 ...
0
votes
1answer
42 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 ...
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}}+ ...
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 ...
1
vote
2answers
84 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
72 views

How does one prove that $2\uparrow\uparrow16+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers. I was reading some things (link) when I came across the footnote on page 21, which states the following: ...
10
votes
3answers
383 views

BMO2 2016 Number Theory Problem

Suppose that $p$ is a prime number and that there are different positive integers $u$ and $v$ such that $p^2$ is the mean of $u^2$ and $v^2$. Prove that $2p−u−v$ is a square or twice a square. Can ...
1
vote
1answer
38 views

estimation for n-th prime

The famous theorem of Hadamard and Vallee-Poussin https://en.wikipedia.org/wiki/Prime_number_theorem implies that $p_n\sim n\ln n$, so $C_1 n\ln n \le p_n \le C_2 n\ln n$ holds for all $n\ge 2$ with ...
0
votes
2answers
37 views

On analogy between $\Bbb Z$ and $\Bbb F_q[x]$

There are objects and operations analogous between $\Bbb Z$ and $\Bbb F_q[x]$. For example primes in $\Bbb Z$ and irreducibles in $\Bbb F_q[x]$ are analogous and so is multiplication operation. ...
1
vote
2answers
40 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 ...
0
votes
0answers
13 views

How the sieving part of quadratic sieve actually works?

I am trying to implement quadratic sieve algorithm as it's described in wiki. I understand most of it, except the part of the sieving example. In the example they use $N = 15347$ with base prime ...
1
vote
1answer
69 views

Are there prime gaps of every size?

Is it true that for every even natural number $k$ there exists some $n \in \mathbb{N}$ such that $g_n = p_{n+1} - p_n = k$? I don't know how to approach the problem at all, and in fact I don't even ...
0
votes
1answer
65 views

Suppose that $n$ is a factor of $(n-1)!+1$. Prove that $n$ is prime [duplicate]

This is in an Algebra and Combinatorics module and I don't know how to prove this. The full question is, Let $n$ be a natural number greater than $1$. Suppose that $n$ is a factor of $(n-1)!+1$. ...
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 ...
-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 ...
1
vote
1answer
30 views

$C(n)+P(n)+S(n)$ always composites?

Let $C(n)$ be the concatenation of first $n$ primes, let $P(n)$ be the product of first $n$ primes, and let $S(n)$ be the sum of the first $n$ primes. It is not surprising that $C(n) - P(n) - S(n)$ is ...