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
1answer
11 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 ...
2
votes
2answers
55 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
votes
2answers
53 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
55 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
13 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 ...
9
votes
1answer
73 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
158 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
39 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
25 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
65 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 ...
6
votes
1answer
102 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
29 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
26 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
17 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
80 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
121 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
79 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
35 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 ...
2
votes
1answer
69 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: ...
3
votes
2answers
73 views

Least number $k>11$, such that $k+n$ is prime for $n=0,2,6,8,12,18,20,26,30,32$

The least integer $k>11$, for which $k+n$ is prime for $n=0,2,6,8,12,18,20,26,30,32$, is, according to my search, $k=33,081,664,151$. The numbers form a prime constellation with length $10$ and ...
10
votes
3answers
375 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 ...
8
votes
3answers
415 views

Find all values x, y and z which satisfy the equation $(x^2 + 1)(y^2 + 1) = z^2 + 1$ given that $(x^2 + 1)$ and $(y^2 + 1)$ are both primes.

Find all positive integers x, y, z which satisfy the equation $(x^2 + 1)(y^2 + 1) = z^2 + 1$ given that $(x^2 + 1)$ and $(y^2 + 1)$ are both primes. It seems trivial that the only set of integers x, ...
0
votes
2answers
36 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. ...
2
votes
1answer
89 views

Explicit form for $\sum_p \ln(\ln(p))$?

Riemann gave an explicit form for the counting function of the primes. Is there an explicit form for the counting function $f(x) = \sum_p \ln(\ln(p))$ where the sum is over $p$ : the number of primes ...
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
48 views

A conjecture about quadratic residues given $p \equiv 5 \pmod 8$

Original Problem $p$ is a prime that is congruent to $5$ modulo $8$ and $a$ is a quadratic residue modulo $p$. Prove that excactly one of $x_1=a^{\frac{p+3}{8}},x_2=(2a)(4a)^{\frac{p-5}{8}}$ is the ...
1
vote
3answers
102 views

If $2n+1$ and $4n+3$ are prime, then $2n-1$ and $4n+1$ are not when $n>2$

How do you prove that, for $n>2$, if $2n+1$ and $4n+3$ are prime numbers, then $2n-1$ and $4n+1$ are composite numbers?
1
vote
1answer
178 views

Showing that $45083$ is prime

The question is: Does $\;x^2 + 10x + 15 = 0\pmod{45083}\;$ have a solution? I can rearrange this to $(x+5)^2 = 10\pmod {45083} \;$ so if I can show that $10$ has a square root mod 45083, I'm done. ...
16
votes
2answers
2k views

Can every even integer be expressed as the difference of two primes?

Can every even integer be expressed as the difference of two primes? If so, is there any elementary proof?
1
vote
1answer
47 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 ...
2
votes
4answers
84 views

Probability that a Mersenne number is prime

Let $p$ be a prime and let $M_p = 2^p-1$ be a (Mersenne) number. Is there any known result on the probability that $M_p$ is prime? In particular is it known whether the probability tends to $1$ as $p ...
0
votes
1answer
64 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$. ...
27
votes
2answers
699 views

Fibonacci $\equiv -1 \mod p^2$

Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify. EDIT: In response to ...
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 ...
1
vote
1answer
60 views

math theory- primes problem

I have tried to prove it for over $15$ hours with no success. I got a clue to use the following technique: between $((P_n), \:2(P_n))$ there is an additional prime hiding there - $P_{n+1}$. ...
1
vote
0answers
28 views

Modular and prime prove [duplicate]

Suppose that $p$ is prime and $p=n^2 +5$ for some natural number $n$, prove that the final digit of $p$ is equal to $1$ or $9$ which is $p=1(mod10)$ or $p=9(mod10)$ What I have to tried so far: in ...
21
votes
2answers
15k views

Has anyone found a “pattern” in prime numbers?

Yesterday I was having some fun trying to look for some patterns in primes; and I think I found something interesting (to me at least). I still have not found any lists of patterns already found, ...
3
votes
2answers
54 views

Find solutions of $2^m\cdot p^2+1=q^5$

$2^m\cdot p^2+1=q^5$ $p$ and $q$ are prime numbers find $p$ and $q$ I think it will be useful to transfer $1$ to the other side of the equation $2^m\cdot p^2=(q-1)(q^4+q^3+q^2+q+1)$ and we know ...
-1
votes
1answer
40 views

Find all $a$, so $q$ prime number which ,$q\times n= aaaaaaa$ [duplicate]

I need your helping to find all the $a$ numbers,which follow the next rules: there is prime number $ 2\lt n\in \mathbb N$ and $ 5\neq q\in \mathbb N$ so that the digits of $n\times q$ are only $a$. ...
0
votes
2answers
65 views

Prove that there is prime number and natural so $n\times q$ digits are $1$.

I need your helping to prove that there is a prime number $ 2\lt n\in \mathbb N$ and $ 5\neq q\in \mathbb N$ so that the digits of $n\times q$ are only $1$. for example:if $n=3$ then $3\times 37=111$ ...
0
votes
0answers
29 views

On primes between consecutive $n-th$ powers. [duplicate]

The Opperman conjecture, is the statement that for every integer $x\geq 2$, there always exists a prime btween $x^2$ and $(x+1)^2$. How about for every integer $n\geq 3$, is there always a prime ...
0
votes
1answer
26 views

What is an upper bound for number of prime powers and semi primes in the interval $[n^2+1,n^2+n]?$

What is an upper bound for number of prime powers in the interval $[n^2+1,n^2+n]?$ What is an upper bound for number of square free semi primes in this interval$?$
-2
votes
1answer
24 views

Is $3x^2 - 3x +1$ is the $4x-4$ th prime for $x>1$? [closed]

I have a prob with this statement. Is this true for all $x>1$ ? If it is... I need a proof.
25
votes
1answer
977 views

A continued fraction involving prime numbers

What is the limit of the continued fraction $$\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{5+\cfrac{1}{7+\cfrac{1}{11+\cfrac{1}{13+\cdots}}}}}}\ ?$$ Is the limit algebraic, or expressible in terms of e or ...