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

0
votes
0answers
31 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
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
43 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
124 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
85 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
41 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
74 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
386 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
39 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
417 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
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. ...
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
179 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
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 ...
2
votes
4answers
85 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
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$. ...
27
votes
2answers
708 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
31 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
57 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$?$
25
votes
1answer
978 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 ...
17
votes
5answers
387 views

Which of the following is not a prime number?

Which of the following is not a prime number ? $a.)\ 911 \ \ \ \ \ \ \ \ \ \ b.)\ 919 \\ \color{green}{c.)\ 943} \ \ \ \ \ \ \ \ \ \ d.)\ 947$ This was asked in my exam and the time given per ...
2
votes
2answers
76 views

What is the probability of being prime?

Given some arbitrarily large $a$, what is the probability that this number is a prime number? My attempt involves seeing that for $a$ to be prime, then it must not have a factor $N$ in the following ...
4
votes
2answers
54 views

What integers are coprime to the first $x$ prime numbers?

I have noticed that there is a very specific pattern to numbers that are coprime to $2$, it is simply all of the odd numbers. More specifically, it is in the following pattern, where $n$ is an ...
2
votes
3answers
69 views

Some hints for “If a prime $p = n^2+5$, then $p\equiv 1\mod 10$ or $p\equiv 9\mod 10$”

I tried to prove this question by first considering the possible last digit of $p$ when $p=n^2+5$, but that reasoning got me nowhere. Then I tried to prove it by contrapositive, and however I just ...
3
votes
1answer
71 views

Asymptotic relation for the following series?

Questions Is the asymptotic relationship correct? How do I determine $c_1$ and $\kappa$? As, $|s| \to 0$ $$ \sum_{r=1}^\infty s^r \ln(r) \sim c_1 \sqrt{s} + (\kappa - 1 + \frac{\ln(2 \pi)}{2} ...
2
votes
1answer
42 views

Density of numbers with exactly $n$ distinct prime factors in $\mathbb{N}$

It is quite well known that the density of the primes in $\mathbb{N}$ is $0$, that is, $$\lim_{n\to\infty}\frac{|\{p\mid p\leq n, p \text{ prime}\}|}{|\mathbb{N}_{\leq n}|}=0$$ It is less well-known, ...
5
votes
2answers
141 views

If $a^4 + 4^b$ is prime, then $a$ is odd and $b$ is even.

We say an integer $p>1$ is prime when its only positive divisors are $1$ and $p$. Let $a$ and $b$ be natural number not both $1$. Prove that if $a^4+4^b$ is prime, then $a$ is odd and $b$ is even. ...
0
votes
0answers
13 views

Truncating Legendre's Formula

Let $p_n$ denote the $n^{th}$ prime. Legendre's Formula, $\phi(x,a)$, counts the number of integers less than or equal to $x$ that are not divisible by the first $a$ primes. Define therefore ...
3
votes
1answer
90 views

Is $\sum_{p}\frac{1}{p!}=\frac{1}{2!}+\frac{1}{3!}+\frac{1}{5!}+…$ irrational?

Is there known way to determine whether the infinite sum below is rational or not? $$\sum_{p}\frac{1}{p!}=\frac{1}{2!}+\frac{1}{3!}+\frac{1}{5!}+...$$
0
votes
1answer
107 views

What would the Riemann Hypothesis mean for the Prime Number Theorem?

The Prime Number Theorem states $\pi(n)\sim \dfrac{n}{\ln n}$. Would there be an equally simple expression if Riemann's Hypothesis were proved true? From Chebyshev Function, would $\pi(n)\sim ...
1
vote
2answers
67 views

Largest Mersenne composites with prime exponent?

I understand that it is an open problem whether there are an infinite number of composite numbers of the form $2^p-1$ with $p$ prime. Is it possible to find examples of such numbers that are much ...
2
votes
0answers
52 views

infinitude of primes with the form $n^2+1$ [closed]

Is there any progress in proving the infinitude of prime numbers of the form $n^2+1$ ?
7
votes
2answers
331 views

Prime numbers in Collatz sequences

This question/request is twofold. First, if this is a stupid question or if it has been addressed before, please say so (bluntness is optional), and I will crawl back into my cave... My question: is ...
-5
votes
1answer
136 views

Can I belive that : $e^{e^{e^{e^{\cdots}}}}$ is $\infty$? [closed]

Definetly this number : $e^{e^{e^{e^{\cdots}}}}$ is not an integer this implies that is not prime number or perfect number , now i would like to know really what is the nature of this number ...