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

10
votes
6answers
641 views

Define an infinite subset of primes such that the sum of reciprocals converges

How can we define an infinite subset of primes such that the sum of reciprocals converges? $S=\{p\in \mathbb{Z}^+ : p\ \text{is prime and some condition on}\ p\}$ s.t. ...
2
votes
1answer
36 views

Integers Free of Small Prime Factors

I am trying to understand (a version of) the elementary proof of the Prime Number Theorem. I've been following Tenenbaum and Mendès France's book The Prime Numbers and Their Distributions. My goal is ...
4
votes
1answer
58 views

Is it possible to sum the divergent series with prime coefficients?

This is a follow-up of this question. It is known that the divergent series $$ P := \sum_{n=1}^\infty p_n \qquad \text{where } p_n \text{ is the $n$th prime} $$ cannot be summed by means of (prime) ...
4
votes
1answer
81 views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
1
vote
1answer
21 views

Reducing fractions with prime number denominators into additions of unities.

So I'm working on practicing reducing fractions into additions of unities (like ancient greek math). It's actually very enjoyable, except when I end up running into a fraction with a prime number as ...
3
votes
5answers
79 views

Finite sequences of prime numbers

There is a lot of prime sequences: prime numbers in a special form. For example Mersenne primes are primes of the the form $2^n-1$, or Pythagorean prime are primes of the form $4n+1$. Even primes are ...
6
votes
1answer
61 views

The number of combinations $(a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n$ such that $a \cdot b = 0$

This question is about a ring for some chosen $n \in \mathbb{N}$ I wanted to find the number $M_n$ of combinations $(a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n$ can be found such that $a \cdot b = 0$ ...
0
votes
0answers
30 views

Primorial mod $2^{32}$

Is $p_n\#$ (primorial - product of $n$ primes) periodic $\pmod{2^{32}}$? It's periodic $\pmod2$ and $\pmod4$, however it don't seems periodic $\pmod8$ and greater modulus.
4
votes
3answers
75 views

Prove that there are infinitely many primes $P_i\equiv1\pmod6$

Proving that there are infinitely many primes is fairly simple: Assume that there is a finite number of primes. Let $G$ be the set of all primes $P_1,P_2,\ldots,P_n$. Compute $K = P_1 \times P_2 ...
10
votes
3answers
2k views

Why are all non-prime numbers divisible by a prime number?

In Euclid's infinite prime numbers proof, the logic is as follows: Assume a set $S$ of all prime numbers in existence is finite (there are a finite amount of primes) Then there must be a greatest ...
3
votes
1answer
67 views

Consecutive Prime Problem

Consecutive primes whose quotient of their product and sum is itself a prime number. $$ 2 \times 3 \times 5 = 30 $$ $$ 30/10 = 3 $$ $$ 3 \times 5 \times 7 = 105 $$ $$ 105/15 = 7 $$ Question: ...
2
votes
1answer
38 views

The perimeter of triangle $ABC$ where $|BC|=293$, $|AB|$ is a square, $|AC|$ is a power of $2$, and $|AC|=2|AB|$

In triangle $ABC$ length of side $BC$ is $293$ (a prime). If length of side $AB$ is a perfect square, length of side $AC$ power of 2 and $AC$ twice length of $AB$, find the perimeter. Kind of ...
1
vote
2answers
46 views

series for $n$-th prime number and prime counting function

"Theoretical Computer Science Cheat Sheet" gives the following: $$p_n = n \ln n + n \ln \ln n - n + n \frac{\ln \ln n}{\ln n} + \mathcal{O}\left( \frac{n}{\ln n}\right)$$ $$\pi (n) = \frac{n}{\ln n} + ...
2
votes
0answers
63 views

Are there infinite many primes p such that 2p-1 is also prime?

I did a search online and found a similar notion called Sophie Germain prime, which by definition is a prime $p$ such that $2p+1$ is also prime. Sophie Germain primes are conjectured to be of infinite ...
0
votes
0answers
24 views

For an integer n ∈ N define P(n) = {primes p : p is a factor of n}. [duplicate]

In other words, P(n) is the set of primes dividing n. For example P(12) = {2, 3} and P(1) = ∅. (a) Write down P(30) and P(32). (b) Consider the relation R on Z defined by n R m if and only if P(n) = ...
4
votes
0answers
56 views

What are major algebraic number theory attempts, results and progressions toward Goldbach's Conjecture?

To my understanding, most progress toward Goldbach's Conjecture has been made in analytic number theory. Progress has often based on sieve, asymptotic estimation or other analytic methods. What are ...
1
vote
1answer
24 views

Can the natural numbers be defined in terms of the non-trivial zeta zeros?

Can the natural numbers be defined in terms of the non-trivial zeta zeros? Presumably they can, since $\pi(x)=\operatorname{R}(x)-\sum_{\rho}\operatorname{R}(x^\rho),$ and $\zeta(s)=\sum ...
0
votes
2answers
33 views

If an integer $a$ is coprime with an integer $b$, then will the integer $a$ also be coprime with the integer $9a + b$?

If an integer $a$ is coprime with an integer $b$, then will the integer $a$ also be coprime with the integer $9a + b$ ?
0
votes
1answer
43 views

Prime Number Primality Testing

I've developed a code and method that works in tandem with an earlier prime number algorithm I developed here: ...
8
votes
0answers
251 views

Sorting of prime gaps

Let $g_n $ be the $n^{th}$ prime gap $p_{n+1}-p_n.$ If we re-arrange the sequence $ (g_n)$ so that for any finite $n$ the gaps are arranged from smallest to largest we have a new sequence ...
4
votes
2answers
44 views

Heuristic for Dirichlet's Theorem on Arithemtic Progression

If we let $\pi_{a,d}(x) = \{p \leq x: p \mbox{ prime, } p \equiv a \mod{d}\}$ then it is a well known result that if $(a,d)=1$ then $$\lim_{x \to \infty} \frac{\pi_{a,d}(x)}{\pi(x)} = ...
0
votes
1answer
14 views

Is the Legendre sieve explicit?

The Wikipedia page for the Legendre sieve... http://en.wikipedia.org/wiki/Legendre_sieve ...says that the Legendre sieve gives upper and lower bounds on the number of primes in a given range. In ...
0
votes
4answers
70 views

Number theory divisibility - simple way to prove this is prime?

Suppose that $y$ is a positive integer, and $z$ is the largest factor of $y$ such that $z<y$, then let $x=y/z$. Prove that $x$ must be a prime number. Is there a simple way to solve this? It ...
5
votes
1answer
214 views

Showing unique prime factorization in first-order logic?

Suppose I have the symbols $\{\neg, \rightarrow, =, <,\cdot, \leftrightarrow,\land, \lor \}$ and functions $Div(x,y)$ ($x$ divides $y$), $Prime(x)$ true if $x$ is a prime, and domain $\mathbb{N}$. ...
3
votes
1answer
57 views

Is sum of square of primes a square of prime?

I would like to know if it has been proved that : There are no $a$, $b$ and $c$, all prime numbers, such that $a^2 + b^2 = c^2$ There are no $a$, $b$, $c$ and $d$, all prime numbers, such that $a^2 ...
10
votes
3answers
320 views

Consecutive Prime Gap Sum (Amateur)

List of the first fifty prime gaps: 1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4. My ...
2
votes
1answer
65 views

The Prime Numbers Set is infinite. Is this proof correct?

Proposition: The Prime Numbers Set is infinite. Proof: Suppose we have a finite set of prime numbers $p_{1}, p_{2}, ..., p_{n}$ such that $p_{n}$ is the largest of them. Define $ c := ...
17
votes
4answers
456 views

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq$ divides $2^{p-1}+2^{q-1}-2$?

A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:- Do there exist infinitely many pairs of primes $(p,q)$ such that ...
0
votes
1answer
225 views

How to determine whether a number can be written as a sum of two squares?

I know the following theorems: A number can be represented as a sum of two squares precisely when $N$ is of the form $n^2 \prod p_i$ where each $p_i$ is a prime congruent to 1 mod 4 If the equation ...
4
votes
0answers
113 views

Differences between large numbers with many factors has little factors

I apologise beforehand for the informality and lack of precision in this question but it is that way because it comes from only an intuition, nothing more than a heuristic argument. Say one has two ...
3
votes
2answers
243 views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
2
votes
3answers
29 views

Given all the multiples of a prime number $p \in \mathbb{Z}$, is $p\mathbb{Z}$ an ideal of $\mathbb{Z}$?

So I'm having a little trouble understanding the concept of an ideal. The book gives the "classic example" of $2\mathbb{Z}$, the even integers, saying these form an ideal. Would I be correct in ...
0
votes
1answer
34 views

Is it possible to represent subsets of natural numbers as groups with prime generators?

I'm learning group theory and I'm trying to consider the "symmetry" of a certain group of natural numbers: Here's the idea, all natural numbers are comprised of multiples of primes. So a subset would ...
0
votes
0answers
37 views

Explanation of a proof of the existence of reclusive primes

The goal is to prove: For any given number $N$, there exists a prime number that is at least $N$ greater than the previous prime number and at least $N$ smaller than the following one. We call those ...
5
votes
4answers
364 views

Solutions to $p+1=2n^2$ and $p^2+1=2m^2$ in Natural numbers.

$$p+1=2n^2$$$$p^2+1=2m^2$$ Find positive integers $m,n$ and prime $p$ satisfying the above two equations. What would people commonly do? Subtracting both the equations. You get: ...
1
vote
1answer
171 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
10
votes
5answers
2k views

Disproving the claim that the numbers 1+2+4, 1+2+4+8, 1+2+4+8+16… alternate between prime and composite

I am working through an elementary number theory book and I have come across the following problem. Show the following claims are wrong: Claim 1: The sequence 1+2+4, 1+2+4+8, 1+2+4+8+16, ...
3
votes
2answers
47 views

Automorphisms of $\langle \mathbb{N}, \cdot \rangle$

It is an elementary fact that multiplication in $\mathbb{N}$ is commutative: $$(\forall n,m)\ n \cdot m = m \cdot n$$ This - among other things - implies that the representation of an $n \in ...
1
vote
1answer
59 views

prime division problem

$a,b,c \in$ {0,1,2,...,9} with at least one of $a,b,c$ nonzero. Prove that the six-digit integer $abcabc$ is divisible by at least 3 distinct primes. My thinking is not to use induction as there is ...
12
votes
5answers
1k views

Why is Euler's Totient function always even?

I want to prove why $\phi(n)$ is even for $n>3$. So far I am attempting to split this into 2 cases. Case 1: $n$ is a power of $2$. Hence $n=2^k$. So $\phi(n)=2^k-2^{k-1}$. Clearly that will ...
4
votes
0answers
154 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
0
votes
1answer
35 views

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$? Would you use $\lim_{x\to \infty}\frac{\pi(x)\log(1-\frac{1}{x})}{\frac{1}{\log x}} = 1$? and how would you show this? Can you ...
1
vote
1answer
60 views

Induction on prime numbers

To dive straight into the question: is there a form of induction which works on prime numbers? I've thought, and while I'm pretty sure it can be done om numbers such as even numbers or numbers ...
21
votes
6answers
2k views

Percentage of primes among the natural numbers

How high is the percentage of primes in $\mathbb{N}$? ($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$) The percentage has to be lower ...
1
vote
1answer
41 views

A better way to prime factorize a set of numbers?

Let's say I have a range of numbers starting from 1 to 10^9 and I need to prime factorize each one of them.My basic algorithm is: 1.Use prime-sieve algorithms(Atkins or Eratosthenes(segmented ...
28
votes
5answers
719 views

Can a Mersenne number ever be a Carmichael number?

Can a Mersenne number ever be a Carmichael number? More specifically, can a composite number $m$ of the form $2^n-1$ ever pass the test: $a^{m-1} \equiv 1 \mod m$ for all intergers $a >1$ ...
35
votes
3answers
3k views

Is $n! + 1$ often a prime?

Related to this question, I wonder how often $n!+1$ is a prime? There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not... or anything in that sense...
1
vote
1answer
59 views

Implementing a function in PARI/GP

I want to define a function: $$g(n)= \begin{cases} +1 & \text{if $n=1$},\\ +1 & \text{if $n$ is an odd indexed prime}, \\ -1 & \text{if $n$ is an even indexed prime},\\ (-1)^r & ...
1
vote
1answer
116 views

Andrica's conjecture implies Bertrand's Postulate?

Let $p_n$ denote the $n$th prime. Recall Andrica's conjecture, which states that $$\sqrt{p_{n+1}}-\sqrt{p_n}<1\quad\text{ for all }\,n.$$ I think Andrica's conjecture implies Bertrand's postulate. ...
1
vote
2answers
55 views

$2p-2$ as the sum of consecutive prime numbers

Progress: Let $p$ be a prime such that $p≡1$ (mod 6) then $2p-2$ can be written uniquely (up to the order of addends) as the sum of some consecutive prime numbers. These are first ten examples: ...