Prime numbers are natural numbers greater than 1 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
2answers
148 views

Why can't $x^2+y^2+z^2$ be prime?

If $x,y,z, a$ are non-zero integers such that $$\frac{x}{z}=\frac{x^2+y^2}{z^2 + a^2}$$ why can't $x^2+y^2+z^2$ be prime? We assume that $x \ne z$. This seems to hold but I can't see how to prove ...
3
votes
1answer
137 views

Digits of $\pi$ forming primes?

Let $f(n)$ be the first $n$ digits of $\pi$ . How many times is $f(n)$ prime on the interval $[1, k]$ ? Are there infinitely many prime $f(n)$'s on $[1, \infty)$? I know this is probably be a very ...
1
vote
2answers
96 views

What is the least prime containing the digitsequences 00..99?

The least prime containing all the digits 0..9 is 10123457689 What is the least prime containing all the digitsequences 00..99 in its decimal representation ? An example is the following prime ...
2
votes
2answers
144 views

Let $p$ be the largest prime less than or equal to $n$. Is $n$ $\underline{<}$ $p^2$

Fix $n$ to be some positive integer greater than or equal to 2. Let $p$ be the largest prime less than or equal to $n$. Is $n$ $\underline{<}$ $p^2$?
2
votes
2answers
110 views

Prime number theorem and how many primes are close to $x$ for sufficiently large $n$

The prime number theorem states: $$ \lim_{x-> \infty}{\frac{\pi(x)}{\frac{x}{ln(x)}}} = 1 $$ I was trying to get a better understanding on the intuition on that statement and more importantly, I ...
3
votes
1answer
717 views

Why is Euler's totient function equal to (p-1)(q-1) when N=pq and p and q are prime? [duplicate]

Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it requires ...
4
votes
5answers
2k views

Properties of the euler totient function

Why is it that the euler totient function has the following condition true based on its definition? $$ \phi(p^k)=p^{k-1}(p-1) = p^k(1-\frac{1}{p}) = p^k-p^{k-1} $$ A proof would be awesome and an ...
-1
votes
1answer
94 views

Application of convergence of Fibonacci series

'There are infinite prime numbers' is a fact that can be deduced by 'reciprocal of primes diverges' statement, so from this can we deduce the fact that --> 'there are finite Fibonacci numbers in ...
0
votes
2answers
101 views

Relating calculus to RSA and/or prime factorization?

I'm writing a math paper on RSA and it would be nice if it had some calculus in it. Is RSA directly related to calculus in any manner? This can include proving theorems, generating keys, or cracking ...
2
votes
2answers
126 views

definition of primes for higher hyperoperations

I was reading yesterday when I came across the history of counting. There was some evidence of an early understanding of prime numbers. I thought that I would try changing the definition of primality ...
6
votes
2answers
148 views

Polynomial is prime when evaluated at prime numbers

Let $P(x)$ be a polynomial with integer coefficients such that $P(p)$ is prime for all prime $p$. What are all possible polynomials $P(x)$? Certainly $P(x)=x$ and $P(x)=p$ with $p$ prime satisfy that ...
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$, ...
1
vote
0answers
80 views

Decomposition subgroup of Cyclic Galois Extension

My question: Say we have a cyclic Galois extension of degree $n$ over $\mathbb{Q}$. Denote the Galois group as $G$. If $H\leq G$, then does there exist a prime, $q$ in $\mathbb{Z} \subset \mathbb{Q}$ ...
7
votes
1answer
107 views

Prime chains with large gaps

It is well known that the gap between consecutive primes is unbounded. Is this still true for a chain of consecutive primes ? More Formally : Is the following statement true for all natural numbers ...
1
vote
0answers
110 views

Estimations for the number of prime factors, counted with multiplicity (elementary combinatorics)

If $N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid$, where $\Omega(n)$ is the number of prime factors (counted with multiplicity) in $n$, I am trying to reason a crude under-estimate for large $k$ and ...
1
vote
1answer
27 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 ...
2
votes
2answers
68 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 ...
4
votes
2answers
1k views

How many perfect squares divide 1!2!3!4!5!6!7!8!9!

What I naturally did was to find the prime factorisation of the product of factorials which is $ 2^{30}3^{13}5^5 7^3 $. Clearly there is 15 unique perfect squares that divide $2^{30}$, 6 unique ...
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
53 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 ...
15
votes
3answers
459 views

A prime of the form $38111111\ldots$

Let $z(n)$ denote the number given by $38$ followed by $n 1$'s. What is the least number $n$, such that $z(n)$ is prime ? With brute force, I checked up to $7000$ digits and did not find a prime. ...
1
vote
1answer
356 views

what the RH equivalent for Riemann prime formula $\Pi(x)$?

Question follow the one answered already, zeros about Riemann Zeta function and some L-function Let's me try my best to make it clear on what I am asking. In his 1859 paper "On the Number of Primes ...
1
vote
0answers
31 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
4answers
12k views

What is the sum of the prime numbers up to a prime number $n$? [duplicate]

How to find the sum of prime numbers up to a prime number $n$, that is for example: the sum of prime numbers up to 7 is: 2+3+5+7=17. So what is the formula for finding: $$\sum_{k=0}^n p_k=????,$$ ...
2
votes
1answer
63 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
168 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 ...
4
votes
0answers
146 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 ...
56
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 ...
12
votes
2answers
172 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
105 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
165 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
213 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
160 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
4k 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
129 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
199 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
378 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
85 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
52 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
713 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, ...
1
vote
1answer
63 views

Finding errors in primality tests?

How do you know when a primality test generates a number that is not prime?
8
votes
1answer
227 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
251 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 ...
97
votes
15answers
9k 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 ...
7
votes
2answers
539 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 ...