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

11
votes
3answers
275 views

Divergence for $p$ prime numbers and convergence for $m$ composite numbers

Does there exist a sequence $(a_n)_{n\in \mathbb N} \in \mathbb C^{\mathbb N}$ such that : For all $p$ prime numbers the series $\displaystyle \sum_{n\in \mathbb{N}} a_n^p$ diverges, and for ...
11
votes
1answer
439 views

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square. I tried brute-force method and tried to find some pattern. I got $p=3,7$ as solutions . Apart from these I have tried for ...
11
votes
3answers
301 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, ...
11
votes
2answers
415 views

Asymptotics of LCM

Let $\operatorname{LCM}(x_1,x_2,\ldots,x_n)$ be the least common multiple of the integers $x_i$. How can one find the asymptotics of $\operatorname{LCM}(f(1),f(2),\dots,f(n))$ as $n$ approaches ...
11
votes
2answers
618 views

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis if at all?

How would proving or disproving the Twin Prime Conjecture affect proving or disproving the Riemann Hypothesis? What are the connections between both conjectures if any?
11
votes
3answers
242 views

Prove or disprove: $99^{100}+100^{101}+101^{99}+1$ is a prime number

Prove or disprove: $$99^{100}+100^{101}+101^{99}+1$$ is a prime number. My idea: let $100^{101}=x^{x+1}$,then $$99^{100}+100^{101}+101^{99}+1=(x-1)^{x}+x^{x+1}+(x+1)^{x-1}+1$$ is prime number? I ...
11
votes
2answers
745 views

crazy problem - does it have a solution? number theory perhaps?

A few researchers are trying to crack a code which involves discovering the values of three integers. They know they are between 1 and 100 (inclusive), and that they may be the same. They each have a ...
11
votes
1answer
352 views

The Goldbach Conjecture and Hardy-Littlewood Asymptotic

A source I am reading refers to the Goldbach conjecture (that every even number is the sum of two primes), and then immediately follows with the "Hardy-Littlewood conjecture" that $\sum ...
11
votes
1answer
678 views

What's the probability that a sum of dice is prime?

Prompted by today's Minute Math question on the MAA site (http://amc.maa.org/mathclub/5-0,problems/T-problems/T-web,ia/2005web/tb05-12-ia.shtml), I started thinking about the probability that the sum ...
11
votes
1answer
286 views

Is there any theoretical indication that this conjecture of Catalan could be true?

Belgian mathematician Catalan in $1876$ made next conjecture: If we consider the following sequence of Mersenne prime numbers: $2^2-1=3 , 2^3-1=7 , 2^7-1=127 , 2^{127}-1$ then $$2^{2^{127}-1}-1$$ is ...
11
votes
2answers
578 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 ...
11
votes
0answers
318 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) = ...
10
votes
5answers
904 views

Decimal form of irrational numbers

In the decimal form of an irrational number like: $$\pi=3.141592653589\ldots$$ Do we have all the numbers from $0$ to $9$. I verified $\pi$ and all the numbers are there. Is this true in general for ...
10
votes
7answers
596 views

Can true randomness come out of mathematical rules?

For example, prime numbers, they seem very random, and they are defined by a simple set of rules. I can't see how real randomness could exist in the real world, but what about mathematics?
10
votes
6answers
6k views

Is a prime factor of a number always less than its square root?

I was going through the fundamental theorem in Number Theory where any non zero integer n can be represented as a product of distinct primes. A related problem with this theorem is to prove that for ...
10
votes
4answers
836 views

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$ Really speaking, I don't have any clue ...
10
votes
3answers
333 views

Are there any Combinatoric proofs of Bertrand's postulate?

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and ...
10
votes
3answers
566 views

How to prove Chebyshev's result: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n $ as $n\to\infty$?

I saw reference to this result of Chebyshev's: $$\sum_{p\leq n} \frac{\log p}{p} \sim \log n \text{ as }n \to \infty,$$ and its relation to the Prime Number Theorem. I'm looking into an ...
10
votes
4answers
1k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
10
votes
9answers
901 views

A Poster About Prime Numbers [closed]

We're going to design a poster about prime numbers, which will appear in a mathematics magazine for middle school students. The poster should be both visually attractive and mathematically rich. Do ...
10
votes
2answers
1k views

Do 4 consecutive primes always form a polygon?

Related to this question, if 4 segments have length of 4 consecutive primes, can they always form a 4-vertex polygon? This question occurred to me out of sheer curiosity, but now I can't prove or ...
10
votes
3answers
501 views

prove that $\lim_{x\to\infty} \pi(x)/x=0$

I think I might have asked this question before, but I can't find it on the site, so I sincerely apologize if I am making a duplicate. But anyway, I have been working on this proof for several weeks ...
10
votes
2answers
362 views

Distribution of primes?

Do primes become more or less frequent as you go further out on the number line? That is, are there more or fewer primes between $1$ and $1,000,000$ than between $1,000,000$ and $2,000,000$? A proof ...
10
votes
2answers
305 views

Take any number and keep appending 1's to the right of it. Are there an infinite number of primes in this sequence?

Ignoring sequences that are always factorable such as starting with 11, Can we take any other number such as 42 and continually append 1s (forming the sequence {42, 421, 4211, ...}) to get a sequence ...
10
votes
2answers
416 views

A problem about the largest prime factor of $n^2+1$

Let $f(n)$ be the largest prime factor of $n$. The image of function $g(n)=\sqrt{f(n^2+1)}$ is like this: Question: If we want to draw a horizontal line which bisects the points from $n=1$ to ...
10
votes
3answers
1k views

How to find the solutions for the n-th root of unity in modular arithmetic?

$$\begin{align*} x^n\equiv1&\pmod p\quad(1)\\ x^n\equiv-1&\pmod p\quad(2)\end{align*}$$ Where $n\in\mathbb{N}$,$\quad p\in\text{Primes}$ and $x\in \{0,1,2\dots,p-1\}$. How we can find the ...
10
votes
2answers
558 views

Mapping natural numbers into prime-exponents space

Take any natural number $n$, and factor it as $n=2^{e_1} 3^{e_2} 5^{e_3} ... p^{e_i}$, where $i$ is the $i$-th prime. Now map $n$ to the point $n \mapsto (e_1,e_2,\ldots,e_i,0,\ldots)$, where $i$ is ...
10
votes
1answer
327 views

What is the intuitive meaning of “conspiracy” in number theory?

Assuming very little number-theoretic background from my part, could you please explain me what is the intuitive meaning behind "conspiracy" in number theory? There is no formal entry on Wikipedia and ...
10
votes
2answers
408 views

Is the set of all numbers which divide a specific function of their prime factors, infinite?

Consider a number $n$ with prime factorization $n=p_1^{k_1} \cdot p_2^{k_2} \dots \cdot p_z^{k_z}$. We define a function $f(n)$ to be $f(n)=(p_1^{k_1+1}-1) \cdot (p_2 ^{k_2 +1}-1) \dots \cdot ...
10
votes
2answers
215 views

Probability p+k is a prime

If p is a prime number, and k is an even integer, what is the probability p+k is a prime number? According to my simulations p+108 is prime twice as often as p+344
10
votes
5answers
248 views

Is there a single or best reason that 2 is an exceptional prime?

I've recently been studying some elementary number theory, and I've frequently come across the fact that there are a fair number of results (the main one being the law of quadratic reciprocity) for ...
10
votes
1answer
294 views

Primes of the form 1..1

For $n \ge 1$ an integer, let's denote $u_n = \sum_{k = 0}^{n-1} 10^k$ That is $u_1 = 1$, $u_2 = 11$, $u_3 = 111$, $u_4 = 1111$, ... My question is the following : Which of them are prime numbers ? ...
10
votes
2answers
212 views

About prime factor and consecutive integers

The problem is: There exists an integer $N$ such that for any $n>N$, there exists $m \in \{n,n+1, \ldots ,n+9\}$ such that $m$ has at least $3$ distinct prime factors. 2 Years ago, My ...
10
votes
2answers
200 views

Are closed geodesics the prime numbers of Riemannian manifolds?

I wonder to what extent one can support the analogy that primitive closed geodesics are the prime numbers of Riemannian manifolds? ("Primitive": traced once, as opposed to $m$-fold for $m \ge 2$.) In ...
10
votes
1answer
495 views

Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?

Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, ...
10
votes
2answers
251 views

The Fermat prime 257 and binomial sum $\sum_{n=0}^\infty \frac{(-1)^n}{\binom {8n}{4n}}$?

We have, $\begin{aligned} \sum_{n=0}^\infty \frac{(-1)^n}{\binom n{n/2}} &= \frac{4}{27}(9-\pi\sqrt{3}\,)\\[2.5mm] \sum_{n=0}^\infty \frac{(-1)^n}{\binom {2n}n} &= \frac{4}{5} - ...
10
votes
1answer
162 views

For each $n$, does there exist a prime $p$ and integer $k$ such that $p^k - 1$ has exactly $n$ prime divisors?

Let $n \geq 1$ be some integer. Can we always find a prime power $p^k$ such that $p^k - 1$ has exactly $n$ distinct prime divisors? For example: $n = 1$ example: $2^2 - 1 = 3$ $n = 2$ example: $5^2 ...
10
votes
1answer
1k views

Would proof of Legendre's conjecture also prove Riemann's hypothesis?

Legendre's conjecture is that there exists a prime number between $n^2$ and $(n+1)^2$. This has been shown to be very likely using computers, but this is merely a heuristic. I have read that if this ...
10
votes
1answer
109 views

Possible values of difference of 2 primes

Is it true that for any even number $2k$, there exists primes $p, q$ such that $p-q = 2k$? Polignac's conjecture talks about having infinitely many consecutive primes whose difference is $2k$. This ...
10
votes
1answer
379 views

Polar Density of a Set of Primes

In Chapter 7 of Marcus' Number Fields, he defines the polar density of a set $A$ of primes of a number field $K$ as follows: Definition: If some $n$th power of the function $$\zeta_{K,A}(s) = ...
10
votes
2answers
127 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 ...
10
votes
2answers
271 views

Where can I find the modern proof of the prime number theorem?

Terence Tao described a modern proof of the prime number theorem in a lecture in UCLA, which is stated in wiki(enter link description here). From wiki: In a lecture on prime numbers for a general ...
10
votes
4answers
2k views

How can one efficiently generate n small relatively prime integers?

The definition of small is that they have O(lg n) bits. One way is just to test the integers 2,3,... for primality and keep the first n primes, but this takes at least O(n log n) time (times the cost ...
10
votes
0answers
238 views

Primes as quotients

I ask this question based on a comment of David Speyer in another question. What primes are of the form $$ \frac{p^2-1}{q^2-1} $$ where $p$ and $q$ are prime? The first prime not apparently of this ...
9
votes
5answers
3k views

Why do we consider prime numbers important, and what are their applications other than number theory in pure math?

Why do we consider prime numbers important, and what are their applications other than number theory in pure math? I know that Number theory is devoted to studying prime numbers, but there must be ...
9
votes
4answers
830 views

Why does “the probability of a random natural number being prime” make no sense?

I read an essay about prime numbers. In it the author suggests that a natural first question to ask is, What is the probability of a random natural number being prime? but proceeds to dismiss ...
9
votes
5answers
212 views

Are numbers of the form $n^2+n+17$ always prime

Someone claimed that a number, multiplied by the number after it plus 17 is always prime, and showed several cases. I'm not a complete amateur in Number Theory, and I know that $17*18+17=17*19$, so it ...
9
votes
5answers
392 views

Is it true that for every prime number $p >3$, the next one will be less than $p+p/2$?

I know that for every prime $p$, the next prime is less than $2p$. Can we improve this statement? Can it be less than $(3/2)p$? What is the best function of $p$ for which this is true (for every ...
9
votes
2answers
207 views

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime?

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime? While answering @pedja's question about the existence of any such representations I was ...
9
votes
3answers
222 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 ...