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

5
votes
0answers
175 views

Understanding Newman's proof of the prime number theorem

I am trying to understand D.J. Newman's proof of the prime number theorem, as presented by D. Zagier. I am not too familiar with analysis, and so there are some things I don't understand. In (III), ...
19
votes
4answers
2k views

Are primes randomly distributed?

There is a famous citation that says "It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990) I have this very ...
5
votes
0answers
285 views

Maximum length of sequence of non-coprimes of $N$ - least upper bound for Jacobsthal's function

I am looking at the length of the longest sequences of adjacent integers that are not coprime to $N$ for very large $N$. Let $F_N$ be the set of integers less than $N$ which are not coprime with $N$: ...
6
votes
2answers
329 views

Efficient way to compute $\sum_{i=1}^n \varphi(i) $

Given some upper bound $n$ is there an efficient way to calculate the following: $$\sum_{i=1}^n \varphi(i) $$ I am aware that: $$\sum_{i=1}^n \varphi(i) = \frac 12 \left( 1+\sum_{i=1}^n \mu(i) ...
2
votes
1answer
39 views

Regularity of matrix with coefficients from GF$(p)$

I have matrix $A$ (its size is $n \times n$) with coefficients from GF($p$), where $p$ is prime. How can be proven that this matrix has all lines linearly independent iff det$(A)\neq 0 $(mod $p$). I ...
1
vote
3answers
195 views

Simplify, expressing answers in terms of powers of primes?

So I'm not really sure how to express these two expressions in terms of powers of primes. Help? $16\cdot25\cdot5^2$ and $24^5$
3
votes
0answers
221 views

What is the catch in this geometrical/number theory question?

Here is a simple geometrical construction: $CA \perp x$ and $DE \perp OC$ As a result: $\bigtriangleup CDE \cong \bigtriangleup CAO$, because $\angle CDE=\angle CAO=\frac{\pi }{2}$ and $\angle ECD$ ...
2
votes
1answer
182 views

Challenging the Chebychev function / prime number theorem?

The prime number theorem accords with the following equation for the first Chebychev function that: $$\lim_{x\rightarrow\infty}\frac{\vartheta(x)}{x}=1 \qquad (1)$$ According to Muñoz García, E. and ...
3
votes
5answers
4k views

What is the mathematical formula to find the sum of the first 1000 prime numbers?

I am trying to improve my coding skills at codeeval (doing practice problems). One of the programming questions I have to answer is to write code that will sum the first 1000 prime numbers. What is ...
5
votes
1answer
112 views

Number of prime factors of difference of two numbers

As is the custom, define $\omega(m)$ to be number of distinct primes dividing $m$. Also, let $P(m)$ represent set of primes divisors of $m$. Let $S=\{p_1,p_2,\ldots,p_n\}$ be a set of $n$ distinct ...
4
votes
1answer
321 views

Euler's sum of divisors recurrence relation

Euler came up with following recurrence relation for the sum of divisors $$\sigma(n) = \sigma(n−1) + \sigma(n−2) − \sigma(n−5) − \sigma(n−7) \dots$$ Since $\sigma(p) = p+1$, where $p$ is a prime ...
1
vote
3answers
173 views

Are there any integer solutions to $\gcd(\sigma(n), \sigma(n^2)) = 1$ other than for prime $n$?

A good day to everyone! Are there any integer solutions to $\gcd(\sigma(n), \sigma(n^2)) = 1$ other than for prime $n$ (where $\sigma = \sigma_1$ is the sum-of-divisors function)? Note that, if $n = ...
1
vote
1answer
190 views

Why prime number theorem tends to one?

I am curious about prime numbers so i just started reading about it. While reading some articles i came across prime number therom (PMT) which states like this $$\displaystyle \lim_{n \to \infty} \pi ...
3
votes
2answers
615 views

Primality test square root of n

I was reading about primality test and at the wikipedia page it said that we just have to test the divisors of $n$ from $2$ to $\sqrt n$, but look at this number: $$7551935939 = 35099 \cdot 215161$$ ...
2
votes
2answers
48 views

Does $((x-1)! \bmod x) - (x-1) \equiv 0\implies \text{isPrime}(x)$

Does $$((x-1)! \bmod x) - (x-1) = 0$$ imply that $x$ is prime?
1
vote
2answers
30 views

Does $n=n^2 - (n!\;\bmod n^2)\implies\text{isPrime}(n) = \text{True}$?

With integers $n$, of such form that $$n=n^2 - (n!\mod n^2)$$ Is $n$ always a prime number?
2
votes
1answer
131 views

The relation of $\zeta$-function and $p^k$ for $Re(s) \le 1$?

The von Mangoldt function: $$\Lambda(n) = \begin{cases} \log p &; \mbox{if }n=p^k \mbox{ for some prime } p \mbox{ and integer } k \ge 1, \\ 0 &; \mbox{otherwise.} \end{cases}$$ establishes a ...
3
votes
2answers
303 views

Do you know Legendre's conjecture ? Has it been proved?

Legendre's conjecture: proposed by Adrien-Marie Legendre, states that there is a prime number between $n^2$ and $(n + 1)^2$ for every positive integer $n$. Has it been proved?
4
votes
1answer
178 views

Explicit formulas for primitive roots?

For a Fermat prime or an "upper" Sophie Germain prime a primitive root is explicitly known. Are there further results when the factorization of p-1 is known? Is it unlikely that we ever get explicit ...
2
votes
1answer
135 views

For any arbitrary large, even gap, are there an infinite number of prime pairs separated by that gap?

Since Zhang Yitang announced his proof that there are an infinite number of prime pairs with gaps less than 70 million, there's been a lot of work toward possibly proving the twin prime conjecture ...
2
votes
2answers
95 views

$x^2+y^2=p$ has a solution in $\mathbb{Z}$

Show that $x^2+y^2=p$ has a solution in $\mathbb{Z}$ if and only if $ p≡1 \mod 4$. Thnx, if someone can help
19
votes
1answer
808 views

Are there prime lengths in triangle with all integer sides and heights?

Suppose you have a triangle in which all sides and all heights are integer in length (i.e. triangle with sides 20, 25, 15 has heights 15, 12 and 20). Could it be that at least one of those numbers is ...
5
votes
2answers
158 views

How common (dense) are undecidable propositions in Peano Arithmetic?

Godel, Turing Rosser et al proved they exist. Are they more like the primes, infinite in number, but getting rarer and rarer as you go along? (Consider larger and larger propositions?) Or are they ...
2
votes
1answer
75 views

Sampling labeled items on a conveyor belts

I have items on a moving conveyor belt. Every item has a label with a number that goes from $1$ to $N$; on the conveyor belt there are more than $N$ items. I have a camera above the items on the belt, ...
0
votes
1answer
59 views

when would next integer $n+1$ be a prime in a given range of $p_*< p< p_*^2$?

Conjecture that along the sequence of natural numbers $n\in\Bbb N$, if walking upwards $1,2,3,4,\ldots,n,n+1,\ldots,$ from every integer to the next (starting with $n=1$), the probability $\phi_p$ ...
6
votes
1answer
163 views

When does $x^2+2y^2 =p$ have a solution in integers?

Show that $x^2+2y^2=p$ has a solution in $\mathbb{Z}\;$ if and only if $\;p \equiv 1 \; \text{or} \; 3 \mod 8$. Can someone help on this. Thnx.
7
votes
1answer
230 views

Can exceptionally large primes be used to get information on the roots of $\zeta$?

Take a list $L$ of roots of the $\zeta$ function, like the ones provided by Andrew Odlyzko and plug it into the Prime Counting Function $\pi(x)$ given by $$ \pi(x) \approx \operatorname{R}(x^1) - ...
6
votes
2answers
127 views

How many distinct translates of a (non-admissible) set $\mathcal{H}$ can consist entirely of primes?

In a recent post, Terence Tao talks about the prime tuples conjecture, and in particular, he asks: "Suppose one is given a ${k_0}$-tuple ${{\mathcal H} = (h_1,\ldots,h_{k_0})}$ of ${k_0}$ distinct ...
10
votes
6answers
892 views

Is there always a prime number between $p_n^2$ and $p_{n+1}^2$?

The following table indicates that there is a prime number p between the square of two consecutive primes. $$ \displaystyle \begin{array}{rrrr} \text{n} & p_n^2 & p_{n+1}^2 & \text{p} \\ ...
3
votes
2answers
142 views

Estimation of the number of prime numbers in a $b^x$ to $b^{x + 1}$ interval

This is a question I have put to myself a long time ago, although only now am I posting it. The thing is, though there is an infinity of prime numbers, they become more and more scarce the further you ...
10
votes
3answers
256 views

Where is the fallacy in the argument using Prime Number Theorem

I am reading about Prime Number Theorem from book by Ingham. As as application of PNT I found the following theorem: Now my doubt is at the step $\frac{\log(y)}{\log(x)}\rightarrow 1$, we can say ...
7
votes
1answer
79 views

Prove that the non-trivial root of $\sum_{k=1}^{2n} p_kx^k=0$ tends to $-1$

I looked at $$ \sum_{k=1}^{2n} p_kx^k=0, $$ where $p_k$ is the $k$th prime. I found that, next to the trivial root $x_0=0$, there is only one more root $x_n$ that tends towards $-1$, when $n$ ...
0
votes
2answers
54 views

Redistribution/synchronization problem

I have a very peculiar problem. I am interested to solve problems such as: B>8 (first occurence of B>8) for 40*B = 15*D such that B and D are integer numbers. The problem is also illustrated in the ...
0
votes
1answer
193 views

is the divisibility of two ditinct primes an independent event?

In a post of April I rasied a question of "The meaning of the Euler Formula for Zeta?" anon brought an absolutely beautiful explanation, with the first part: "Heuristically, if $p$ and $q$ are ...
1
vote
3answers
409 views

“Goldbach's other conjecture” and Project Euler - writing 1 as a sum of a prime and twice a square

From Problem 46 of Project Euler : It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square. $$9 = 7 + 2 \cdot ...
4
votes
4answers
196 views

I found out that $p^n$ only has the factors ${p^{n-1}, p^{n-2}, \ldots p^0=1}$, is there a reason why?

So I've known this for a while, and only finally thought to ask about it.. so, any prime number ($p$) to a power $n$ has the factors $\{p^{n-1},\ p^{n-2},\ ...\ p^1,\ p^0 = 1\}$ So, e.g., $5^4 = ...
-1
votes
1answer
88 views

$\log$ transform of the fundamental theorem of arithmetic? [closed]

Taking the canonical form of the fundamental theorem of arithmetic in the form: $$n=\prod_{j=1}^\infty p^{m_j}_j \qquad ;m_j\in \Bbb N_0$$ Does anybody know about a $\log n$ transform of this? Note: ...
2
votes
1answer
51 views

Error in understanding the theorem about the invertibility of an element(coset) of a quotient ring

There's a theorem in Abstract Algebra which states that: An element of a quotient ring $\mathbb{Z}/\langle n \rangle$ or $\mathbb{Z_n}$ that is a coset $\overline{a}$ is invertible iff $a$ and $n$ ...
1
vote
3answers
834 views

Prime generating functions

I'm studying prime numbers at school and I've seen some functions that generate mostly prime numbers. I'm talking about : $$\text{Euler's polynomial : } n^2+n+41$$ $$\text{Legendre's polynomial : } ...
1
vote
0answers
57 views

Ring of the residual classes $(\Bbb Z/p\Bbb Z)^\times$? $p$-adic integer?

In a recent question we raised the theorem: for a given prime $p$ and a given power $m$ the representation of any positive integer $n\in \Bbb N$ in the form: $$ n=(a_u p - b_u) \; p^m$$ is unique ...
1
vote
1answer
92 views

connect p-adic expansion and fundamental theorem of arithmetic?

On the way to explain a $p$-adic expansion, we consider, when dealing with natural numbers, if we take $p$ to be a fixed prime number, then any positive integer expansion in the form can be written as ...
2
votes
0answers
31 views

Does the sum over the normed differential of the prime power function equal $2\log2\pi$?

Let $p\in \Bbb P$ a prime and a prime power function: $$\xi_p(x) = p^x$$ with $x \in \Bbb R^+_0$ hence: $$\xi'_p = \frac{d}{dx}\xi_p=\xi_p \log p$$ Taking into account E. Muñoz García and R. ...
-1
votes
2answers
67 views

Differential of product function of prime powers?

Taking my prior question, here comes follow up: Let $p\in \Bbb P$ a prime and a prime power function: $$\xi_p(x) = p^x$$ with $\xi_p\in \Bbb R^+$ and $x \in \Bbb R^+_0$ hence: $$\xi'_p = ...
1
vote
2answers
144 views

Is polynomial $1+x+x^2+\cdots+x^{p-1}$ irreducible? [duplicate]

Let $p$ a prime number, is the polynomial $$1+x+x^2+\cdots+x^{p-1}$$ irreducible in $\mathbb{Z}[x]$ ? Thanks in advance.
0
votes
2answers
215 views

Combination of positive integers in terms of primes (sophisticated version 2)

Here comes a second sophisticated version of my conjecture, as critics came up the first version was trivial. Teorem 2 for a given prime $p$ and a given power $m$ the representation of any positive ...
1
vote
3answers
62 views

Conjecture on combinate of positive integers in terms of primes

Along a heuristic calculation, I am struggeling with a possible proof for my following conjecture: Every positive integer $n\in \Bbb N$ can be written as a unique combination of $a,b \in \Bbb N$, ...
0
votes
2answers
51 views

Solving A Linear Congruential System

I need to find a prime p which makes: $p\equiv {\pm1}\text{ (mod }8)$ and $p\equiv {\pm1}\text{ (mod }12)$ How could I find such $p$? Is there any specified method I can use? I'd be grateful if ...
15
votes
4answers
565 views

Need help understanding Erdős' proof about divergence of $\sum\frac1p$

I'm looking at proofs from Proofs from the Book (Martin Aigner, Günter M. Ziegler). The proof I'm having trouble is the sixth proof of the infinitude of the primes they give (on page 5; although I'll ...
2
votes
1answer
827 views

How do you prove that there are infinitely many primes of the form $5 + 6n$?

There should be infinitely many primes of the form $5+6n$. How do you prove it? The same should be true for $7+6n$.
4
votes
2answers
87 views

Choosing $a$ s.t. $\frac{a^k - 1}{a-1}$ is not a prime power

Let us suppose that we are presented with a positive integer $k$ and asked to come up with a positive integer $a$ such that $\frac{a^k - 1}{a-1}$ is not a prime power, or just to prove in an ...