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

8
votes
2answers
1k views

Proof that there are infinitely many primes of the form $4m+3$

I am reading a proof of there are infinitely many primes of the form $4m+3$, but have trouble understanding it. The proof goes like this: Assume there are finitely many primes, and take $p_k$ to be ...
4
votes
3answers
2k views

Can Prime numbers be negative?

I was wondering, can a prime number be negative? We had a question over at security.se which stated that prime generation with openssl: openssl dhparam -text 1024 ...
0
votes
1answer
43 views

How many terms are required to get $D$ digits of Riemann zeta prime function?

How many terms are required to get $D$ digits of Riemann zeta prime function $\zeta_p(s) = \sum_p \frac{1}{p^s}$? Sebah & Gourdon mentions that finding $\zeta_p(2)$ to 20 digits by using $\sum_p ...
1
vote
1answer
55 views

Prime number generation - speed comparison

"Efficient prime number generating" leads to some algorithms being displayed as "fast". Up to PG7.8 which does takes 65786 seconds to generate the prime numbers > ...
6
votes
4answers
183 views

Tell whether $\dfrac{10^{91}-1}{9}$ is prime or not?

I really have no idea how to start. The only theorem considering prime numbers I know of is Fermat's little theorem and maybe its related with binomial theorem. Any help will be appreciated.
0
votes
1answer
40 views

Asymptotic sum of the squares of the first n primes [closed]

I know there is an asymptotic formula for the sum of the squares of the first n primes, but I have been unable to find it.
3
votes
1answer
59 views

Greatest common divisor problem involving $a^p+b^p$ [closed]

Let $\gcd(a,b)=1$ for some $a,b\ \epsilon \ \mathbb{N}$. Prove that for any odd prime p: $$\gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)=1,~~~~ \text{or} ~~~p.$$
1
vote
1answer
66 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 ...
4
votes
7answers
105 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 ...
3
votes
1answer
59 views

Inequality with prime numbers

I found exercise in my book for number theory that I can't resolve. How do you show that $$p_n < e^{1+n}$$ where $p_n$ is $n$-th prime number?
0
votes
0answers
19 views

Could you give a definition of what is a superior highly composite number using only words?

I know very well what is a superior highly composite number, but I would like to see how could we (roughly) define what is a superior highly composite number using only words (using no equations and ...
2
votes
1answer
33 views

Firoozbakht's conjecture and maximal gaps

In the Wikipedia article, it seems to me as if it's implied that it is enough to check the conjecture only for maximal gaps (numbers $n$ s.t. $\forall k<n:g_n>g_k$). I.e it holds that ...
10
votes
3answers
358 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
4answers
52 views

system of congruence - my approach

We have: $$k^3 + l^3 \equiv 0 \pmod{17}\\ k^2 + l^2 \equiv 0 \pmod{17} $$ And I get: $$k = 17n+r_k\\ l = 17m+r_l$$ And I analyzed possible rests respect to system of congruences. My result is: $$ ...
8
votes
3answers
1k views

Why does Euclid write “Prime numbers are more than any assigned multitude of prime numbers.”

In Euclid's Elements Book XI proposition 20 (http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html), Euclid proves that: Prime numbers are more than any assigned multitude of prime ...
0
votes
0answers
27 views

Difference between two (not consecutive) primes

I am searching for an lower bound on the difference between the $(n+k)$-th and $n$-th prime number in terms of $k$. I have something like this in mind (conjecture): Let $(p_k)_k$ denote the ...
2
votes
5answers
1k views

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$
0
votes
3answers
104 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?
2
votes
1answer
109 views

Between $n$ and $2n$ there is always a prime number. [duplicate]

Between $n$ and $2n$ there is always a prime number. I was thinking of this and looked it up on the google to find that this is true. Now, I am wondering what is the proof for it? Does any ...
2
votes
1answer
259 views

is it possible to get the Riemann zeros

since we know that the number of Riemann zeros on the interval $ (0,E) $ is given by $ N(E) = \frac{1}{\pi}\operatorname{Arg}\xi(1/2+iE) $ is then possible to get the inverse function $ N(E)^{-1}$ ...
2
votes
2answers
120 views

Prime larger than a twin prime

Wondered whether the following equation holds true for all twin primes such that where $a$ and $b$ are twin primes and where $b=a+2$, then $3\left[\left(\frac{a+b}{2}\right)^2-1\right]+2 = NP$. Where ...
1
vote
2answers
67 views

I want to get a formula for solving this

If $abc = n$ where $a,b,c,n\in \mathbb{N}$ then can you derive a formula to find the total number of triples of a,b,c as such? eg : $abc = 12$ has $4$ such triples, ...
4
votes
1answer
66 views

Factors of integers of the form $2^n-1$

I came across a problem where i had to tell the number of divisors of $2^i-1$ which are of the form $2^j-1$. I saw many contestants using the fact that if $i$ is divisible by $j$ then $2^i-1$ is ...
5
votes
2answers
257 views

Prime sum identity

Let $ \Lambda(k) $ denote the von Mangoldt function: $$ \Lambda(k) \stackrel{\text{def}}{=} \begin{cases} 0 & \text{if $ k $ is not a prime power}, \\ \ln(p) & \text{if $ k = p^{j} $}. ...
0
votes
1answer
37 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
70 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 ...
0
votes
2answers
222 views

find a general expression for the remainder when a prime divides a fibonacci.

I have primes of form $5k\pm1$. Consider the equation: $F_n=f(n)\pmod p$ where $F_n$ is the nth fibonacci number. Now given a c, how can i check whether or not there exists a solution for $f(n)=c ...
11
votes
7answers
755 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. ...
38
votes
2answers
2k 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?
2
votes
2answers
44 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 ...
4
votes
1answer
79 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 ...
0
votes
2answers
75 views

Prove that if $p$ is prime, and $a^2=b^3$

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 ...
2
votes
1answer
40 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
71 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
119 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
22 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 ...
6
votes
1answer
65 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
36 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
76 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
83 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
45 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
47 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 ...
1
vote
1answer
27 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
35 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
45 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
47 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
17 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
3answers
75 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 ...