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

2
votes
1answer
80 views

Disjoint subset/prime question

If $p$ is a prime, which integers $n$ is it possible to split the set consisting of $\{1,2,...,n\}$ into $p$ disjoint (meaning they have no element in common) subsets where the sum of the integers in ...
0
votes
2answers
140 views

Twin Prime Conjecture's Proof [closed]

I've found this article that claims to have a proof of the Twin Prime Conjecture. Can you find any error? (I have some doubts about the last page of the paper...)
4
votes
1answer
126 views

Can the twin prime conjecture be solved in this way?

After some research, I have discovered that proving the statement; There exist an infinite number of positive integers K such that; $K \neq 6ab \pm a \pm b$ and $K \neq 6ab \mp a \pm b$ is ...
11
votes
4answers
1k views

Is it true that the book 'Calculate Primes' has found the pattern?

I read about a book called 'Calculate Primes' by James McCanney. It claims to have cracked the pattern for generating families of primes, and also the ability to factorize large numbers. ...
2
votes
1answer
64 views

Proving a statement about prime numbers

Let $p_1,p_2,p_3,\cdots$ be all the primes sorted in an increasing order. Is $p_1p_2p_3\cdots p_i + 1$ is always prime? Why? How can I prove that?
7
votes
3answers
186 views

If a prime can be expressed as sum of square of two integers, then prove that the representation is unique.

If a prime can be expressed as sum of two squares, then prove that the representation is unique. My attempt: If $a^2+b^2=p$, then it is obvious that $a,b$ of different parity. Now, I assume the ...
-1
votes
2answers
54 views

All primes that cannot be be represented as a specific sum

For $n \in N$, $p_i$ prime, for $i \in N$, find all primes such that can be represented as $p_1 p_2\cdots p_n+p_1 p_2\cdots p_{n-1}+p_1 p_2\cdots p_{n-2}+\cdots+ p_1 p_2 + p_1 + 1$. Source: ...
0
votes
2answers
69 views

Primality of $2^q\pm2^{(q+1)/2}+1$ when $q$ is an odd integer

It can be quite easily shown that $5$ is a divisor of $2^q+2^{(q+1)/2}+1$ iff ($q=8k+1$ or $q=8k+7$) and that $5$ is a divisor of $2^q-2^{(q+1)/2}+1$ iff ($q=8k+3$ or $q=8k+5$). Now, it seems that ...
2
votes
0answers
19 views

Regularities in a prime-exponent graph

Let $\Omega(n)$ be the number of prime factors of $n$ with multiplicity, i.e., if $n=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, $\Omega(n) = e_1 + e_2 + \cdots + e_k$ (OEIS). For example, for $n=9000 = ...
1
vote
0answers
28 views

Find prime pairs satisfying the equation

Find all ordered pairs $(p_{k},p_{k+1})$, where $p_k$ denotes the $k$-th prime, such that for every $m\ \in \mathbb{N}$ there exists $\alpha \in \mathbb{N}$ s.t. $\Omega(\alpha) = m$ so that ...
0
votes
1answer
42 views

A question about an asymptotic formula

I've been told that the asymptotic formula $\pi(x+y)-\pi(x)\sim y/\ln x$ holds for $y\ge x^{1/2+\varepsilon}$ if Riemann's hypothesis is true, but I was unable to find a journal reference for this. ...
4
votes
4answers
33 views

greatest common divisor of two primes a,b

Here is the question I am trying to prove: If $a,b$ are relatively prime and a>b prove that $\gcd(a-b, a+b) \in \{1, 2\}$. Can I begin with something like $(a-b)k + (a+b)l = d$ where $k,l$ are ...
1
vote
2answers
66 views

Is there a name for this type of integer?

An integer $n$ such that $\exists$ at least one prime $p$ such that, $p|n$ but $p^2$ does not divide $n$. i.e. : an integer with at least one prime that has a single power in the prime factorization. ...
2
votes
2answers
39 views

Check if any number of this form is composite

I got this problem to solve saying : Given that $n>2$ and $n$ is a natural number, prove that $y = 2^n + (-1)^{n+1}$ is a composite number. I took the above and I did the following: $$y = 2^n + ...
0
votes
0answers
22 views

Almost-prime based condition met by one integer only

Let $a_{m,n} = T(n,k)$ s.t. $\forall_{l>0}{ T(n,k+l) > m^l * T(n,k)}$, where $k$ is minimal, $T(n,k)$ denotes the n-th k-almost prime $l \in N, m \ge 2$. Prove that $m = 2$ is the only case ...
1
vote
0answers
46 views

How many k-almost primes less than

How many $k$-almost primes are less than $p^k$? If there exists an analytical solution, can it be shown as a function of Fibonacci sequence? Example, for $k \in N$ and $p=3$, we have as follows: ...
1
vote
1answer
38 views

What is the reasoning behind ways of splitting up this summation sign?

Some context: I've been studying Chebyshev's $\psi$ - function, which claims that $\psi(x) = \sum_{n \le x} \Lambda(n) = \sum_{p^k \le x} \log p$ where $p$ is prime and $\Lambda(n)$ is the von ...
3
votes
1answer
41 views

Understanding a plot of composite numbers against the ordinal position of their prime factors

I was toying with primes factors of natural numbers and I have found a graph which caught my interest but one, which I am struggling to understand better. Let us take the composite number $N$=391721. ...
7
votes
1answer
427 views

The largest possible prime gap?

What is the largest possible prime gap if we observe only 1000-digits numbers? There are few conjectures about this question but is there something that we can say and be absolutely sure of it?
8
votes
4answers
230 views

Gaps between primes

I recently watched a video about the recent breakthrough involving the gaps between primes. I have an idea that I'm sure is wrong, but I don't know why. If you take the product of all prime numbers ...
5
votes
1answer
294 views

A club for some special prime numbers: new members welcome

Given an integer $i$, find an integer $n$ ( $2^{j-1}\le n <2^j$), and a prime divisor $p$ of $M_n=2^n-1$, so that $v= j+i$; where $p$ is written as $k2^v+1$, $k$ odd. In other words, $j$ is such ...
1
vote
0answers
86 views

Location of Prime Gaps Subsequence

The primes are : 2,3,5,7,11,13,17,... The prime gaps are thus: 3-2,5-3,7-5,11-7,13-11,17-13,... 1,2,2,4,2,4,... An example subsequence of the prime gaps sequence is: 2,4,2 This subsequence begins ...
2
votes
0answers
34 views

Renyi entropy of prime gaps

Denote with $p_n$ the $n$-th prime number and let $$ h_N(d) = |\{ n : p_{n+1} < N, p_{n+1} - p_n = d \}| $$ be the number of times that prime gap $d$ happens for primes less than $N$. Let $H = ...
0
votes
0answers
20 views

Number of smallest integers created with a fixed number of smallest primes

How many (first) smallest (starting from 2) integers can be created with only (first) smallest $k \in N$ primes? Example below. For k=1 we have only {2} (only one prime), and with it we can create ...
0
votes
0answers
19 views

Reduced residue systems and prime k-tuple bijection

First off, the terminology: Primorials: the products of the first $n$ primes, written as $P_n \#$. Reduced residue system modulo a positive integer $K$: Those numbers smaller than $K$ that are ...
2
votes
0answers
32 views

Infinitude of composite numbers of the form $n\# \pm 1$

Are there infinitely many composite numbers of the form $$n\# + 1$$ where $n$ is a prime number? What about $n\# - 1$? Here $n\#$ denotes the primorial function of $n$, i.e. the product of all ...
6
votes
2answers
121 views

The sequence of prime gaps is never strictly monotonic

I have an assignment question that asks me to show that the sequence of prime gaps is never strictly monotonic. I'm also allowed to assume the Prime Number Theorem. I've managed to show that it ...
5
votes
1answer
173 views

A Conjecture about Maximal Prime Gaps

As it is well known that prime number is $2,3,5\cdots \cdots$, thus all these prime number are denoted by$p_{1},p_{2},\cdots \cdots ,p_{n}\cdots \cdots$. The prime maximal gap $\max_{p_{n+1}\leqslant ...
8
votes
2answers
115 views

Relative sizes of prime gaps

There are no prime numbers between the two primes $113$ and $127$. That gap seems quite large by comparison to the sizes of the numbers in it. $$ \frac{\text{size of gap}}{\text{prime just below the ...
8
votes
1answer
354 views

Improving Zhang's prime gap

I am referring to Zhang's paper. Since the set $\cal{H}$ is a subset of $[3.5\times 10^6, 7\times 10^7]$, shouldn't the prime gap he obtained be less than $ 7\times 10^7 - 3.5\times 10^6$ rather than ...
2
votes
1answer
176 views

Prime gaps distribution

It is well-known that gaps between successive primes have i.e. multimodal distribution (with peaks at $6 k$): I'm interested to know: what is the most suitable approximation for such weird ...
3
votes
3answers
178 views

Modular multiplication with machine word limitations

Imagine I have 64-bit machine and the widest integer available is 64-bit signed long. I cannot use BigInteger or similar libraries for performance reasons, and all calculations I get would me modulo ...
8
votes
3answers
310 views

Prove that $n^2+n+41$ is prime for $n<40$

Here's a problem that showed up on an exam I took, I'm interested in seeing if there are other ways to approach it. Let $n\in\{0,1,...,39\}$. Prove that $n^2+n+41$ is prime. I shall provide my own ...
0
votes
0answers
42 views

Lehmer's Totient Problem

Recently I have been trying to prove the famous Lehmer's Totient Problem by Elementary Methods and surprisingly enough I have found success to some extent. While researching, I have deduced the very ...
43
votes
4answers
2k views

How to understand and appreciate the prime number industry?

Why would I want to buy prime numbers? There is a website (found it!) selling a table of 400 digit primes for twenty dollars. Like an updated version of this. I have a layman's idea that prime numbers ...
45
votes
11answers
9k views

Why is Euclid's proof on the infinitude of primes considered a proof?

I've expressed Euclid's proof on the infinitude of primes on Mathematica: ...
2
votes
2answers
549 views

Disprove the Twin Prime Conjecture for Exotic Primes

The List of unsolved problems in mathematics contains varies conjectures of exotic primes like: Mersenne primes (of the form $2^p - 1$ where $p$ is a prime, A000668, $43\%$) Sophie Germain primes ...
2
votes
0answers
69 views

On Goldbach conjecture

Let $N$ a large natural number, let $\forall n\leq N,\, R_{2}\left(n\right)=\underset{p_{1}+p_{2}=n}{\sum}\log\left(p_{1}\right)\log\left(p_{2}\right)$ and let $S\left(\alpha\right)=\underset{p\leq ...
5
votes
1answer
55 views

Sum of a certain series related to the primes

It is well known that $$\sum_{n > 0}\frac{1}{n}$$ diverges, but $$\sum_{n > 0}\frac{1}{n^2} = \frac{\pi^2}{6}$$ converges. Similarly, $$\sum_{p}\frac{1}{p}$$ diverges, but $$\sum_{p} ...
1
vote
2answers
70 views

Isomorphism between Rings $\mathbb{Z}[\frac{u}{v}]$ and $\mathbb{Z}[\frac{1}{v}]$, u,v relatively prime

Let $u$ and $v$ be relatively prime integers, and let $R'$ be the ring obtained from $\mathbb{Z}$ by adjoining an element $\alpha$ with the relation $v\alpha=u$. Prove that $R'$ is isomorphic to ...
10
votes
5answers
10k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?
3
votes
2answers
567 views

How do you determine if a number is prime or composite?

Is there any way to decipher, manually of course, whether a (large enough) number is a prime?
3
votes
3answers
122 views

Proof that there are infinitely many primes congruent to 3 modulo 4

I'm having difficult proving this. As a hint the exercise to prove first, that if $a\lneqq \pm 1$ satisfies $a \equiv 3 (\textrm{mod}\ 4)$, then exist $p$ prime, $p \equiv 3 (\textrm{mod}\ 4)$ such ...
0
votes
1answer
94 views

Prove that $2^x \cdot 3^y - 5^z \cdot 7^w = 1$ has no solutions

Prove that $2^x \cdot 3^y - 5^z \cdot 7^w = 1$ has no solutions in $\mathbb{Z}^+$, if $y\ge 3$.
1
vote
1answer
43 views

Convergence of product over all primes

How can we find the values of $x$ for which $$\prod_{p \text{ prime}}{1-\frac{x^2}{p^2}}$$ converges? I know that this product $$\prod_{p \text{ prime}}{1+\frac{x^2}{p^2}}$$ converges if and only if ...
16
votes
2answers
586 views

Is there an infinite number of primes constructed as in Euclid's proof?

In Euclid's proof that there are infinitely many primes, the number $p_1 p_2 ... p_n + 1$ is constructed and proved to be either a prime, or a product of primes greater than $p_n$. Trivially, we ...
0
votes
0answers
25 views

Sequence of irreducible polynomials

Does there exist a sequence of nonzero integers $a_n$ such that for all $n$ the polynomial $\sum_{k=0}^n a_k x^k$ is irreducible if: 1) every $a_n$ is prime; 2) all $a_n$ are pair wise coprime; 3) ...
0
votes
1answer
131 views

A question about prime gaps

Recently, I have been reading the Wikipedia article about prime gaps (http://en.wikipedia.org/wiki/Prime_gap) and I came across the following: Hoheisel was the first to show that there exists a ...
0
votes
0answers
42 views

It has been conjectured that there are infinitely many primes in the form $n^2-2$. Exhibit five such primes.

It has been conjectured that there are infinitely many primes in the form $n^2-2$. Exhibit five such primes. I'm so confused what the problem is asking. Do I just need to find examples or an ...
4
votes
1answer
58 views

Sum of Prime Factors - TopCoder

Recently in Topcoder, I faced a problem which stated as follows: "You have a text document, with a single character already written in it. You are allowed to perform just two operations - copy the ...