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

3
votes
0answers
138 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
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 ...
54
votes
5answers
5k views

Is this of any real importance to the mathematical scientific community?

I'm a 31 year old engineer, and I've recently came up with a way to exactly predict the probability of the number of prime numbers between two different integers. For example using my way, the number ...
11
votes
2answers
171 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 ...
2
votes
2answers
93 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 ...
-2
votes
1answer
75 views

Can anyone please determine integral below?

I was creating a paper on P.N.T but I stucked here so,
2
votes
1answer
149 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 ...
1
vote
1answer
203 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 ...
1
vote
2answers
146 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 ...
0
votes
4answers
3k views

Co Prime Numbers less than N

I need to find all the numbers that are coprime to a given $N$ and less than $N$. Note that $N$ can be as large as $10^9.$ For example, numbers coprime to $5$ are $1,2,3,4$. I want an efficient ...
0
votes
1answer
119 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 ...
8
votes
1answer
212 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
2answers
177 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, ...
8
votes
2answers
370 views

How often is a sum of $k$ consecutive primes also prime?

Let's define a $k$-sum as a sum of $k$ consecutive primes. For example, $15=3+5+7$ is a $3$-sum. How many $k$-sums are themselves prime? Here's one way to formulate the question more precisely: What ...
4
votes
1answer
84 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 ...
0
votes
1answer
57 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 ...
1
vote
1answer
42 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
51 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 ...
11
votes
3answers
668 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, ...
0
votes
1answer
62 views

Finding errors in primality tests?

How do you know when a primality test generates a number that is not prime?
8
votes
1answer
220 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 ...
9
votes
1answer
211 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 ...
93
votes
15answers
8k views

Infiniteness of non-twin primes.

Well, we all know the twin prime conjecture. There are infinitely many primes $p$, such that $p+2$ is also prime. Well, I actually got asked in a discrete mathematics course, to prove that there are ...
6
votes
2answers
506 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
101 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
156 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 ...
12
votes
5answers
521 views

How many prime numbers are there in between $1000!+1$ and $1000!+1000$, inclusive?

I know $1000!$ is not a prime number as any number $1000$ or less is a divisor, but how would I know if $1000!+1$ is prime? Any hints? Also, use the above question to prove that you can find $n$ ...
1
vote
2answers
65 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 ...
8
votes
1answer
135 views

Number made from ending digits of primes

Consider the number $0.23571379391713739171393971379371799173739113791379391173917133713717793$ ... The number is formed by the ending digits of the prime numbers. Is it known whether this number ...
3
votes
1answer
74 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 ...
6
votes
1answer
797 views

Divisibility of binomial coefficient by prime power - Kummer's theorem

Let's say we have binomial coefficient $\binom{n}{m}$. And we need to find the greatest power of prime $p$ that divides it. Usually Kummer's theorem is stated in terms of the number of carries you ...
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
0answers
82 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 ...
7
votes
1answer
221 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
3answers
348 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 ...
3
votes
0answers
97 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 \\ ...
19
votes
1answer
796 views

Mandelbrot set and prime numbers

I have written a simple program in C to generate Mandelbrot set. Wherever I zoom in, it seems to me that I see prime numbers, most often 11, 17, 19. For example the object on the attached image has 11 ...
9
votes
4answers
309 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 ...
1
vote
1answer
76 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
97 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?
20
votes
2answers
354 views

Related to greatest prime number that divides $n.$

I don't even have an idea of how to start working on this one: Let $p(n)$ denote the greatest prime number that divides $n.$ Show that there exists infinitely many positive integers $m$ such that ...
57
votes
2answers
959 views

Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers?

Our algebra teacher usually gives us a paper of $20-30$ questions for our homework. But each week, he tells us to do all the questions which their number is on a specific form. For example, last ...
2
votes
2answers
220 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. ...
3
votes
2answers
203 views

Generating function for the characteristic function of primes

What do we know about the generating function of $\chi(n)$ (A010051) $$ f(x) = \sum_{n=0}^\infty \chi(n)x^n = \sum_{p\text{ prime}} x^p $$ for $\chi(n)$ the characteristic function of the primes: ...
6
votes
2answers
982 views

Infinitely many primes of the form $8n+1$

I'm looking at this funny little problem involving proving the existence of an infinite number of primes of a certain form: Prove that there are infinitely many prime numbers expressible in the ...
0
votes
1answer
140 views

Every two consecutive integers are coprime.

I start with knowing that two numbers are coprime if: $n*k + m*j = 1$ So, setting $k = a$ and j = $a+1$ I can solve as follows: $n*a + m*a + a$ Then, $a(n+m) + m = 1$ Where can I go from here?
5
votes
2answers
125 views

Finding mod of X^2+1 = 0 to have exactly 4 solutions

Find a natural number $m$ that is product of 3 prime numbers, and that the equation $x^2+1 \equiv 0 \text { (mod m)}$ has exactly 4 solutions mod m.
6
votes
1answer
104 views

Polynomials over $\mathbb N$ generating no primefactors smaller than $p_0$ - methods for proving?

Studying a family of recurrent sequences (generalized from the NSW-numbers) I came to the observation, that certain polynomials (over $\mathbb N$) avoid primefactors below some smallest one. For ...
0
votes
2answers
165 views

Intermediate Problem Solving Patterns involving Prime Factoring

a and b are positive integers such that $a\times b= 500000000,$ where neither a nor b contain any zeros. Find a and b where $a<b.$