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

A question about $t^x \equiv 1 \pmod {q\#}$ where $t,x$ are integers and $q\#$ is a primorial.

Let $t,x$ be positive integers and $q$ be any prime. I was told that you can solve for $t^x \equiv 1 \pmod {q\#}$ by solving for each prime factor of $q\#$ and then setting $x$ to the least common ...
1
vote
0answers
47 views

Asymptotics for prime factors

Am I correct in assuming that the same result: $$ N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid \ \sim \frac{x}{\log x}\frac{(\log_2 x)^{k-1}}{(k-1)!}\ (x \rightarrow \infty) $$ also holds for: $$ ...
2
votes
2answers
67 views

square of primes above 5

Given that squares of all primes above 5 are either 1 (mod 30) or 19 (mod 30), is this just a curious coincidence, or is there some straight-forward explanation? My research has not lead me to any ...
1
vote
1answer
52 views

Approximating this integral without using Mertens' theorem

Take $p$ as prime, $\text{li}(x)$ as logarithmic integral and $$ R(x)=\sum_{p\leq x}\frac{\ln p}p-\ln x $$ Without using Mertens' theorem find $$ \int_0^x\frac{tR'(t)}{\ln t}dt $$ I tried using ...
1
vote
1answer
48 views

Reference request for proof of Landau's generalised PNT

Could someone please point me in the direction of a proof for Landau's asymptotic formula for k-almost primes: $$\pi_k(n) \sim \left( \frac{n}{\log n} \right) \frac{(\log\log n)^{k-1}}{(k - 1)!}$$ I ...
13
votes
1answer
572 views

Going from $\Lambda$ to a prime count

A 1997 paper of Étienne Fouvry and Henryk Iwaniec, Gaussian primes, concerns the prevalence of primes that are of the form $n^2+p^2$ for prime $p$. The asymptotic result is $$\sum_{n^2+p^2\le ...
11
votes
2answers
160 views

What are Green's almost primes?

In a general-audience talk, Ben Green explains his famous proof with Terence Tao as an application of Szemerédi's theorem, but placing the primes within a smaller set of almost-primes in which they ...
11
votes
1answer
1k views

Euler's remarkable prime-producing polynomial and quadratic UFDs

Good example of a polynomial which produces a finite number of primes is: $$x^{2}+x+41$$ which produces primes for every integer $ 0 \leq x \leq 39$. In a paper H. Stark proves the following result: ...
1
vote
0answers
29 views

A sequence converging to the number of decompositions of $2n$ as a sum of 2 primes

For every even positive integer $n>2$ and every non-negative integer $k$, let's define the sequence $N_{k}(n)$ as follows: ...
2
votes
1answer
61 views

Determination of all prime numbers which give integer solution of a particular summation.

Determine all primes numbers $p$ such that $$p \sum_{k=0}^{n}\frac{1}{2k+1} \in N$$ for a given positive number $n$
3
votes
1answer
145 views

Bound of the sum $\sum_{p\le n}\frac{1}{\log(p)}$

While doing a sum I came to the sum $\displaystyle\sum_{p\le n}\dfrac{1}{\log(p)}$. Where the $\log$ is the natural logarithm. It was easy to prove that $\displaystyle\sum_{p\le ...
14
votes
0answers
404 views

Divergence of the Derivative of the Prime Counting Function

On the one hand, the Prime Counting Function $\pi_0(x)$ maybe be written $$ \pi_0(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho}) \tag{1} $$ with $ \operatorname{R}(z) = ...
1
vote
2answers
129 views

If $2$ divides $p^2$, how does it imply $2$ divides $p$?

I'm trying to understand a proof by contradiction. It's proving by contradiction that $\sqrt2$ isn't rational. (It's a standard proof involving $\sqrt2=\frac{p}{q}$, where $p,q$ are already ...
2
votes
2answers
90 views

Does there exist an infinite sequence $p_0,p_1,p_2…$ of prime numbers such that $p_k=4 p_{k-1}\pm 1$

$k \in Z^+$ firstly we know that there exists infinetly many primes of the form $4n+1$ by FTA also we see that if we consider finite primes say to $n$ then the recursive formular can be expressed ...
3
votes
0answers
128 views

Transcendental numbers involving primes?

Is the prime zeta function value $$ P(2)=\sum_{p \in \mathrm{primes}} \frac{1}{p^2} = 0.452247420041065498506543364832247934173231343\ldots $$ a transcendental number ? What about the following sum ...
-2
votes
1answer
74 views

Can anyone please determine integral below?

I was creating a paper on P.N.T but I stucked here so,
2
votes
0answers
58 views

Prove $\left(\frac{q(q+1)}{p}\right) =\left(\frac{1+q^{-1}}{p}\right )$ for $p\gt2$ a prime, and any $q \in \mathbb{Z^+} $.

For $p\gt2$ a prime, and any $q \in \mathbb{Z^+} $, Show that $\left(\frac{q(q+1)}{p}\right) =\left(\frac{1+q^{-1}}{p}\right )$ where the terms are legendre terms. I saw this result as part of a ...
8
votes
1answer
209 views

Proving infinitude of primes in a certain form.

Here I have the following conjecture -Let $$S_1(n)= \frac{(n-1)! +1}{n}$$ then there exist infinite prime numbers $p$ for which $S_1(p)$ is prime. And I don't know how to prove it. EDIT Let ...
2
votes
1answer
135 views

In a given sequence of consecutive integers, finding the count of integers with a least prime factor greater than $p$

If a number $x$ has a least prime factor of $3$, then it is necessarily of the form $6y+3$ and the next number with a least prime factor of $3$ is $6y+9$. Between these two numbers there are always ...
2
votes
2answers
90 views

Solving infinite sums with primes.

Let $p_n$ denote the $n$'th prime number. How would one go about proving that infinite products like: $$\prod_{k=1}^\infty1 - \frac{1}{(p_k)^2} = \frac{6}{\pi^2}$$ or ...
0
votes
1answer
109 views

Kth Power Coprime with N

Given two integers $N$ and $K$. A function of $N$ and $K$ the sum of K'th powers of the positive numbers, which are coprime with N and also not greater than N. E.g., the Function value for $N=6$ and ...
1
vote
1answer
189 views

Prime Splits Completely in Every Intermediate Field

Suppose I have a finite field extension of number fields (finite field extensions over $\mathbb{Q}$), say $K\subset L$. Say $P$ is a prime in the number ring contained in $K$ such that $P$ splits ...
2
votes
2answers
149 views

An approach to Andrica's conjecture

Andrica's conjecture states that $\sqrt{p_{n+1}}-\sqrt{p_n} < 1$. but solving for $n=1,2,\dotsc$ yields n=1, $\sqrt{p_{2}}-\sqrt{p_1} < 1$=>$\sqrt{p_{2}}<\sqrt{p_1}+1$ n=2, ...
-2
votes
3answers
314 views

Prove or disprove these statements on prime numbers

Conjecture 1: Let p be an odd number. Suppose that there is a positive integer h such that $$ 2^h \equiv p+2 \pmod{p^2}$$ p is a prime number iff there exist an integer k such that $ 2^{h+kp} \equiv ...
4
votes
1answer
77 views

Linnik's theorem for kth prime in the residue class

Linnik's theorm says that for any modulus $m$, the smallest prime in a given residue class mod $m$ cannot be too large: $$ p(a,m)\ll m^L. $$ where $L$ is a constant which has been improved by many ...
52
votes
2answers
6k views

The square roots of different primes are linearly independent over the field of rationals

I need to find a way of proving that the square roots of a finite set of different primes are linearly independent over the field of rationals. I've tried to solve the problem using ...
0
votes
1answer
56 views

Generating of primes in base-3 edited

How to prove the following statement! for example primes $p_1$ = $7$ = $n$ and $p_2$ = $13$ = $2n-1$(each prime is $> 3$), then $m = p_1 p_2$ is a Fermat-pseudo prime in base-3. Can we prove ...
8
votes
1answer
201 views

What is the big picture behind AKS algorithm?

Despite a number of question on AKS algorithm here, there does not seems to anything related to the idea behind it (for those who don't know, AKS primality testing is found in PRIMES is in P). I read ...
22
votes
3answers
462 views

Computing the product of p/(p - 2) over the odd primes

I'd like to calculate, or find a reasonable estimate for, the Mertens-like product $$\prod_{2<p\le n}\frac{p}{p-2}=\left(\prod_{2<p\le n}1-\frac{2}{p}\right)^{-1}$$ Also, how does this behave ...
1
vote
1answer
41 views

Are the conjectural values of $H_{k}:=\lim\inf_{n\to\infty}p_{n+k}-p_{n}$ available somewhere?

The question is in the title. It can be found on the current Polymath 8b project page that one expects to have $H_{1}=2$, $H_{2}=6$, $H_{3}=8$, $H_{4}=12$ and $H_{5}=16$ but I'm interested in larger ...
2
votes
1answer
50 views

how often do we find $p^m - q^n= \pm2$ for primes $p,q$ and $m,n > 1$

if one of the integers $m,n$ is $1$ it does not seem too difficult to find examples of odd primes satisfying: $$|p^m-q^n| = 2$$ so suppose $\min(m,n)>1$, and call (just for the purpose of this ...
0
votes
1answer
55 views

A diophantine equation related to primes.

I have $2$ prime numbers $p_1$ and $p_2$. I have to find the solution of $\large{p_1t_1+p_2t_2=1}$ where $t_1$ and $t_2$ are integers. How do I do this?
11
votes
3answers
558 views

Why are conjectures about the primes so hard to prove?

I recently started learning number theory, and I've noticed there are many conjectures about the prime numbers that are unproven. Some examples would be whether there are infinite Mersenne, ...
9
votes
1answer
180 views

What does this music video teach us about 863?

This delightful animation by Stefan Nadelman depicts "the additive evolution of prime numbers", set to Lost Lander's song "Wonderful World": http://www.youtube.com/watch?v=TZkQ65WAa2Q. (If you haven't ...
6
votes
2answers
414 views

Riemann Hypothesis and the prime counting function

This article on the prime counting function mentions that the Riemann Hypothesis is equivalent to the statement $$|\pi(x)-\rm {li}(x)|\le \frac {1}{8\pi}\sqrt {x}\log (x)\text { for all }x \geq 2657 ...
0
votes
1answer
89 views

Mersenne Primes and Fermat's Little Theorem

This is essentially a two part problem. Prove that $2^{4n+3} = 1$ (mod $8n+7$) with $8n+7$ a prime. Using this prove that $2^{4019} - 1$ is not a Mersenne prime, $4019$ is a prime For ...
2
votes
0answers
142 views

Special matrices with determinant 0

Define a quadratic matrix A with n rows and n columns by filling it with consecutive primes, starting with some prime p. The object is, to find the least starting prime p, such that A has determinant ...
1
vote
1answer
70 views

The progression $4n+3$ and primes.

Consider an arithmetic sequence $4n+3$. This sequence contains infinitely many primes and infinitely many composites. It is clear that there cannot be $3$ consecutive primes in the sequence as every ...
1
vote
2answers
64 views

Proof about congruences

Let $p$ be a prime. Show that for all integers $x$, $x^2\equiv 1 (\text{mod} \ p) $ if and only if $x \equiv 1 (\text{mod} \ p)$ or $ x \equiv p-1 \ (\text{mod} \ p ). $ I know that I have to prove ...
1
vote
1answer
86 views

El-Gamal: Recovering random number r

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
2
votes
1answer
72 views

Let rad(n) = $\Pi_{primes, p|n}$ p.

Let $\operatorname{rad}(n) = \displaystyle\prod_{\stackrel{p|n}{p \text{ prime }}}p$ . I have proven that $\operatorname{rad}(n)$ is a multiplicative arithmetic function. I have also proven that ...
9
votes
4answers
272 views

Estimate of $n$th prime

There is a result that if $p_n$ is the $n$th prime, then $p_n\sim n\log n$ as $n\rightarrow\infty$. I wonder: Is it a direct consequence of the prime number theorem $\pi(x)\sim x/\log x$? The theorem ...
25
votes
1answer
929 views

Is $1847^{2013}+2$ really a prime?

The number $1847^{2013}+2$ is a probable prime. Is it really prime? I started primo, but it seems to slow for this task. I noticed that there is a faster program used to find the primes ...
7
votes
1answer
211 views

Asymptotic formula for almost primes

I have developed a formula for almost primes which is far more accurate asymptotically than Landau's well known $$\pi_k(n) \sim \left( \frac{n}{\log n} \right) \frac{(\log\log n)^{k-1}}{(k - 1)!}$$ ...
2
votes
0answers
74 views

Conjecture similar to Dirichlet's theorem

Dirchlet's theorem states that there are infinitely many primes of the form an+b , where n is a natural number, when gcd(a,b)=1. Let a number which is the product of two distinct primes with the ...
3
votes
0answers
93 views

How generalize the alternating Möbius function?

Here is what I want to do, I have this matrix: $$\displaystyle T = \begin{bmatrix} +1&+1&+1&+1&+1&+1&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ ...
1
vote
1answer
72 views

$\pi(x)$ asymptotic as integral $1/\log t$

From the prime number theorem we know that $\pi(x)\sim x/\log x$, i.e. $\dfrac{\pi(x)\log x}{x}\rightarrow 1$ as $x\rightarrow \infty$. How can we use that to show that ...
-1
votes
1answer
93 views

How to determine the prime numbers? [closed]

What is the best way to determine the prime numbers? Is there a way other than trial-and-error to determine them? Is the set of prime numbers finite or infinite?
2
votes
2answers
170 views

What is the highest power of a prime that divides nPr?

I know that the highest power of a prime which divides $n!$ is given by $$\left[\frac np\right]+\left[\frac n{p^2}\right]+\left[\frac n{p^3}\right]...$$ Where $[x]$ is the greatest integer function. ...
1
vote
3answers
90 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?