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
1answer
64 views

$\left| (4 \mathbb{N} -1) \cap \mathbb{P} \right| \ = \ \infty$ where $\mathbb{P}$ is the set of prime numbers. [duplicate]

I try to show that there are infinitely many prime numbers in the set $ \{ 4n-1 \ : \ n \in \mathbb{N} \}$. I've been told that I needed to adjust Euclid's proof a bit so that it would work for ...
1
vote
5answers
79 views

prove if a|b and b|a then $a = \pm b$

Fairly basic I guess. Attempt: $a\neq\pm b \Rightarrow a\nmid b \vee b \nmid a$ let $a = \pm b + d, d\in \mathrm{Z} \wedge d\neq 0$ then $a\mid b \Rightarrow b\nmid a$ and $b\mid a \Rightarrow ...
2
votes
2answers
173 views

Legendre's formula

Legendre's formula counts the number of positive integers less than or equal to a number $x$ which are not divisible by any of the first $a$ primes: $$\begin{align} &\phi(x,a)=\lfloor x ...
54
votes
4answers
3k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
0
votes
2answers
88 views

If a prime $p\mid b$ and $a^2=b^3$, then $p^3\mid a$

I have an exercise that I don't know how to solve. I tried to solve it in many ways, but I didn't get any progress in proving or disproving this... The exercise is: Prove or disprove: if $p$ is a ...
1
vote
1answer
30 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 ...
9
votes
1answer
2k 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 ...
4
votes
6answers
136 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 ...
11
votes
7answers
858 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. ...
6
votes
1answer
66 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$ ...
1
vote
2answers
74 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
174 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 ...
12
votes
4answers
5k 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
107 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: ...
4
votes
3answers
107 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 ...
2
votes
1answer
73 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 ...
4
votes
1answer
111 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
145 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
31 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
43 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
110 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: ...
4
votes
2answers
60 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)} = ...
1
vote
2answers
80 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 ...
3
votes
1answer
109 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 ...
2
votes
1answer
91 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 := ...
1
vote
3answers
47 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
236 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 ...
6
votes
2answers
4k 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$ ...
3
votes
1answer
79 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 ...
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, ...
1
vote
1answer
77 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 ...
3
votes
2answers
53 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 ...
3
votes
0answers
157 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 ...
0
votes
1answer
40 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
99 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 ...
1
vote
1answer
103 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 ...
1
vote
2answers
116 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: ...
2
votes
2answers
106 views

Do the ratios of successive primes converge to a value less than 1?

I think it's a pretty straightforward question. Does $\lim_{n \to \infty}{\frac{p_n}{p_{n+1}}} < 1?$ ***$p_n$ denotes the nth prime. Since the average gap increases between successive primes by ...
2
votes
1answer
77 views

Algorithm to identify complex Mersenne primes?

I am thinking on the complex analogue of the Mersenne primes. I think, some like a "complex Mersenne prime" could be a complex prime in the form $$2^{a+b\frac{pi}{2}i}-1$$ Where $a+bi$ is a complex ...
0
votes
1answer
48 views

How many distinct lists of 14 integers $L=\{v_1,\ldots ,v_{14}\}$ exist satisfying $v_i \geq v_{i+1}\geq 0$ and $\sum _{i=1}^{14}(v_i) \leq 54$

I am trying to solve the following problem: I have an ordered list of integers $L = \{v_1,\ldots ,v_{14}\}$ with fourteen elements, satisfying the following two conditions: $v_i \geq v_{i+1}\geq 0$ ...
1
vote
1answer
307 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 & ...
0
votes
1answer
88 views

Count numbers with prime digit

Given a number $N$, I need to find the count of the numbers that have atleast one prime digit $2,3,5$ or $7$ in it. Now $N$ can be upto $10^{18}$. What is the best approach to solve this problem. ...
2
votes
1answer
46 views

Finding the lowest number (or an upper bound to the lowest number) not congruent to a set of moduli

Note: if finding x is not possible, an upper bound, where there must be at least one number less than said number which is not congruent to the set, would be helpful. The set: For my purposes, the ...
2
votes
1answer
50 views

Is $\sum_{n=1}^N e^{2 \pi p_n z i}$ bounded for irrational $z$?

Let $p_n$ be the $n$th prime number. If $z$ is irrational real, is it known whether the partial sums $\sum_{n=1}^N e^{2 \pi p_n z i}$ are bounded? It seems the partial sums are unbounded if $z$ is ...
4
votes
2answers
786 views

Fastest way to find if a given number is prime

Given a random number, what would be the quickest possible way of finding out whether it was prime? Obviously, one could just iterate through the number in order to see if it was divisible by ...
10
votes
3answers
803 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 ...
1
vote
2answers
48 views

Asymptotic behaviour of $\prod_{p \leq x} (1 + 4/(3p) + C p^{-3/2})$

I'm reading Montgomery and Vaughan and in it they state quite simply \begin{equation} \prod_{p \leq x} \left(1 + \frac{4}{3p} + \frac{C}{p^{3/2}} \right) \ll (\log x)^{4/3} \end{equation} as $x ...
0
votes
1answer
71 views

Is there a 10-digit emirp?

Does a 10-digit emirp exist? Unfortunately, the lists of emirps I could find on the Web are quite small and my programming skills aren't good enough to write a program to check all the primes up to ...
0
votes
3answers
125 views

$6n+1$ and $6n-1$ prime format [duplicate]

I recently stumbled upon a fact that all prime numbers past $3$ are of the form either $6n-1$ or $6n+1$. Is it true? at least for numbers less than $10^9$. And does it cover all primes?
0
votes
1answer
101 views

What percent of numbers are primes? [duplicate]

I understand that there are infinitely many primes and (obviously) infinitely many integers, but is there any way to calculate the total percentage of integers that are primes? Thanks