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

0
votes
1answer
32 views

References for Legendre's prime-counting function

This question is about Legendre's prime-counting function, the one that can be used to calculate the exact amount of prime numbers that are less than or equal to a given number (as long as the number ...
3
votes
1answer
21 views

Find all $n$ so that $c_n$ $>$ $\pi(n^2)$

Find all $n$ $\in$ $\mathbb{N}$ so that $p_{c_n}$ $>$ $n^2$ where $p_n$ denotes the $n$-th prime and $c_n$, the $n$-th composite. I have tried doing the problem using The stronger version of ...
5
votes
1answer
115 views

Prove that $512^3 + 675^3 + 720^3$ is a composite number

We have to prove that the number $$N=512^3 + 675^3 + 720^3$$ is composite. I tried to use the identity $(a^3+b^3+c^3)=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)+3abc$ hoping to take out some common ...
5
votes
7answers
222 views

Alternative Proof of Infinitely Many Primes? [duplicate]

I've seen Euclid's proof of infinitely many primes, what are other approaches to proving there are infinitely many primes?
3
votes
1answer
52 views

Solutions to $3\cdot 5 p_1 \pm 37^n p_2 =2^b\cdot 29^m p_3$

Let $p_k$ be either primes larger than $40$ or equal to $1$. $n,m$ are larger than $0$ and $b$ is either $1$ or $2$. I'm searching solutions for the following equation: $$ 3\cdot 5 p_1 \pm 37^n p_2 ...
1
vote
1answer
38 views

Euler totient of a number

If $n= \prod_{i=1}^{m} p_i$, all $p_i$ pairwise distinct, then number of coprimes below $n$ is $\prod_{i=1}^{m} (p_i-1)$. For example with $m=2$, there are $p_2-1$ multiples of $p_1$ below $n$ and ...
1
vote
3answers
47 views

If there is an $a\in\mathbb{Z}$ with $a^{n-1}\equiv 1\mod n$ but $a^{\frac{n-1}p}\not\equiv 1$ for all primes $p\mid n-1$, then $n$ is a prime

Let $n\in\mathbb{N}$ with $n\ge 3$ and $a\in\mathbb{Z}$ such that $$a^{n-1}\equiv1\text{ mod } n\;\;\;\wedge\;\;\;a^{\frac{n-1}{p}}\not\equiv1\text{ mod }n\;\;\;\forall p\in\mathbb{P}:p\mid n-1$$ ...
3
votes
1answer
51 views

Conjecture about prime numbers

$$\forall k\in\mathbb{N},k\ge1,\exists p:k^3\lt p\lt (k+1)^3$$ with $p$ prime number. In other words is it possible to prove that for every $k\gt1$, with $k$ integer number it exists a prime number ...
2
votes
0answers
58 views

Is this a conjecture or an already existing one??

Does the following inequality hold? $p(n)\leq 2^n,$ where $p(n)$ is the $n$th prime. If this is true then it follows that: If $p(n)=p(m)^x+p(o)^y$, then $\max[x,y] \le n$.
15
votes
4answers
5k views

How many prime numbers are known?

Wikipedia says that the largest known prime number is $2^{43,112,609}-1$ and it has 12,978,189 digits. I keep running into this question/answer over and over, but I haven't been able to find how many ...
75
votes
5answers
6k views

What is the Riemann-Zeta function?

In laymen's terms, as much as possible: What is the Riemann-Zeta function, and why does it come up so often with relation to prime numbers?
0
votes
1answer
56 views

Under assumption that $\frac{M_{n+1}}{M_n} \le 2$, what is true?

This question was hinted upon with the still open question at [1]. Let $M_n = $ A005250($n$) of the OEIS. That is to say, $M_n = p_{i+1}-p_i$, where $p_i$ is the smallest prime such that $p_{i+1} - ...
0
votes
1answer
36 views

If p is a prime positive integer, find all subfields of GF(p)

If p is a prime positive integer, find all subfields of GF(p) This question just seems too vague.
3
votes
1answer
67 views

1-to-1 correspondence between twin primes and $n^2-1$

I am trying to establish the one-to-one correspondence of twin primes to integers $n$ where $n^2-1$ has 4 divisors. It is clear to me that this is the case, since $$n^2-1=(n+1)(n-1)$$ where the RHS ...
6
votes
1answer
86 views

(Easy?) consequence of the Riemann Hypothesis

I'm trying to show that the relation $\psi(x)=x+O(\sqrt{x}\log ^2 x)$ (consequence of the Riemann hypothesis) implies $\pi(x)=Li(x)+O(\sqrt{x}\log x)$, where $Li(x)=\int_2^x \frac{dt}{\log t}$. I ...
0
votes
1answer
19 views

Relationship between the Carmichael function and Euler's totient function

Let $\lambda$ denote the Carmichael function and $\varphi$ Euler's totient function. Furthermore, let $p$ denote any prime number and $k\in\mathbb{N}$. The wikipedia article about $\lambda$ states: ...
1
vote
1answer
29 views

Any simpler way to do Pollard's p-1 method?

I found calculating factorization by Pollard's p-1 method is almost impossible if use a conventional scientific calculator. For example, I am trying to factor ...
4
votes
1answer
59 views

Primes in an Infinite Set

Let $S$ be the infinite set of positive integers whose members can be written with no digits except $0$ and $1$ and with no more than $1988$ $1s$. Show that some integer $n$ does not divide any member ...
8
votes
2answers
284 views

diophantine equation $ |x^2-py^2|=\frac{p-1}{2} $

Prime $p\equiv3\pmod4$, then diophantine equation $$ |x^2-py^2|=\frac{p-1}{2} $$ has a solution in integers en, $x^2-py^2=-1$ has no solution in integers. I'd be grateful for any help you are ...
2
votes
1answer
64 views

Proof that there are infinitely many primes of the form $6k+1$. Proof verification

Theorem. there are infinitely many primes of the form $6k+1$. I've just proved that there are infinitely many primes of the form $6k+1$. Could you please check my proof? At first, I proved that ...
8
votes
4answers
550 views

Is there always a prime number between $p_n^2$ and $p_{n+1}^2$?

The following table indicates that there is a prime number p between the square of two consecutive primes. $$ \displaystyle \begin{array}{rrrr} \text{n} & p_n^2 & p_{n+1}^2 & \text{p} \\ ...
1
vote
1answer
48 views

On Newman/Zagier's proof of PNT

I have just got this paper: http://people.mpim-bonn.mpg.de/zagier/files/doi/10.2307/2975232/fulltext.pdf and I have a serious doubt: When proving that soft Tauberian theorem he explicitly uses ...
1
vote
1answer
33 views

Divisibility of sum of exponents

Consider the sequence $$r, \ ra, \ ra^2, \ ra^3, ... \ , ra^n \mod M $$ such that: $$ ra^{n+1} \equiv r \mod M$$ and $a \ne 1$ and $a,r$ are both coprime to $M$ Is it always true then that: ...
15
votes
1answer
147 views

The Gaussian moat problem and its extension to other rings in $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$

One of my favourite open problems in number theory, an area in which I enjoy only as a hobbyist, is the Gaussian moat problem, namely "Is it possible to walk to infinity in $\mathbb{C}$, taking ...
1
vote
1answer
29 views

Prove that there is no such positive rational pair and positive odd prime, for which $q_1^p+q_2^p=1$ [closed]

Prove that there is no pair of positive rational numbers $q_1,q_2\in\Bbb{Q}^2$ and positive odd prime $p$, for which $q_1^p+q_2^p=1$
1
vote
1answer
36 views

Number of the form $3k+2$ has a prime factor of the same form

I was thinking of using a proof by contradiction. I will also note that following the book I am using has not covered congruences in case that is the methodology. Let $n=3k+2=ab$. Assume that $n$ ...
6
votes
3answers
129 views

Primes as a difference of powers

Find the smallest prime that cannot be written as $$|3^a - 2^b|$$ EDIT: I forgot to mention that $a$ and $b$ are whole numbers. I tried to expand $3^a$ as $(2+1)^a$ using binomial theorem but ...
1
vote
2answers
58 views

A polynomial formula for the primes

Is there a proof that there is no polynomial which would return $n$th prime for the input value $n$? In other words is there an explanation for why there is no polynomial $P(x)$ such that $P(n)=p_n$ ...
13
votes
1answer
1k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
2
votes
3answers
57 views

How to use Legendre symbol to find a prime which divides $ax^2+b$?

I'm trying to prove that $\dfrac{x^2-2}{2y^2+3}$is never an integer if $x,y\in\mathbb{Z}$. It can be proven if $\forall p\in\mathbb{P}\:$doesn't suffice both of the following congruences: $$\: ...
6
votes
3answers
225 views

What's known about the number of primes in the range $(n..2n)$?

What asymptotic lower bounds are known on the number of primes between $n$ and $2n$, call it $\Pi(n) = \pi(2n)-\pi(n)$? Obviously Bertrand's Theorem is the statement that $\Pi(n) \geq 1$ for all $n$, ...
2
votes
2answers
102 views

Prove that $a^n+b^n \equiv (a+b)^n \mod n$, if $n$ is prime and $a,b$ are integers.

What is the best method to prove that if $n$ is prime and $a,b$ are integers $a^n+b^n \equiv (a+b)^n \mod n$, ?
9
votes
5answers
213 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 ...
1
vote
0answers
33 views

What is the status of research on primes as an example of general sieve-generated sequences?

I have been interested in treating the prime numbers as a special case of sieve-generated sequences, however they may be defined by different authors. Can someone here give me any information about ...
9
votes
0answers
76 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
1
vote
2answers
28 views

Upper bound for the difference between number-of-divisors and sum-of-divisors functions

The number-of-divisors function $d$, and the sum-of-divisors function $\sigma$, are defined by $$ d(n) = \sum_{d \mid n} 1, $$ $$ \sigma(n) = \sum_{d \mid n} d, $$ respectively. Now let $N$ be a ...
1
vote
1answer
20 views

Examine if $\exists M$ such that $\forall n>M$, $\pi(2n)$ $-$ $\pi(c_n)$ $>$ $0$

The problem is- Examine if $\exists M$ such that $\forall n>M$, $\pi(2n)$ $-$ $\pi(c_n)$ $>$ $0$. Also find a value of such $M$ for which the theorem is true. Though I haven't still given ...
-3
votes
1answer
57 views

What's the Shannon entropy of the prime numbers?

Here's a note that calculates it as 1. Do you know of any other calculations? http://www.math-math.com/2014/05/shannon-entropy-shannon-entropy-of.html
1
vote
2answers
40 views

prove that $N$ is divisible by $1,2,\ldots,k$ which $k+1$ is the lowest prime number after $N$

Suppose $n$ is a natural number ($n\ge 5$) and $k+1$ is the lowest prime number that is greater than $n$ prove that $A_i \mid n!$ which $A_i$ are these numbers: $1,2,\ldots,k$
18
votes
1answer
275 views

Mandelbrot set and prime numbers

I have written a simple program in C to generate Mandelbrot set. Wherever I zoom in, it seems to me that I see prime numbers, most often 11, 17, 19. For example the object on the attached image has 11 ...
3
votes
1answer
27 views

Is ${(prime^2-1) \over 24}$ always a member of the generalized pentagonal number set?

I was working through a puzzle on why the square of a prime minus one is always a factor of 24 (http://puzzles.nigelcoldwell.co.uk/fifteen.htm) and noticed that the sequence of numbers for ...
2
votes
3answers
391 views

Proof: if $n=pq$ then $p-1\mid q-1$ and $q-1\mid p-1$

Now I'm asking my first question to understand a specific proof: Let $n=pq$ and $q,p \in \mathbb{P}$. Then we get $p-1\mid n-1$ and $q-1\mid n-1$, because there are prime integers mod $p$ and mod ...
5
votes
2answers
315 views

Proof that no polynomial with integer coefficients can only produce primes

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but ...
1
vote
1answer
74 views

Are there Generalizations of this theorem I found on a chit of paper?

Some time ago , I was reading a book which was not of a mathematical taste from a library . But from that book a chit of paper came out which was handwritten and had the title : Aubry's theorem And it ...
4
votes
1answer
63 views

Question about the proportions of primes p for which $ord_p(2)$ satisfies certain congruences

let $p$ be a prime. I have observed numerically that the proportion of $p$ satisfying $ord_p(2)\equiv4[8]$ seems to be $1/3$. Why is it so? Is there a simple proof? Moreover the proportion $c$ of ...
0
votes
1answer
71 views

Why does the number of divisors of a superior highly composite number is always a highly composite number up to 720720 ? (the only exception is 120)

I've calculated the number of divisors of every superior highly composite number up to $10^{27}$: http://oi59.tinypic.com/ndaijo.jpg The number of divisors of a superior highly composite number is ...
4
votes
4answers
481 views

Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
12
votes
3answers
395 views

Number Theory or Algebra?

Prove that if $4^m-2^m+1$ is a prime number, then all the prime divisors of $m$ are smaller than $5$ I initially thought about putting $4^m-2^m+1=p$ where $p$ is some prime and after eliminating ...
0
votes
1answer
28 views

$\psi(p_{n+1}) - \psi(p_n)$?

Let $$S(p_n)=\psi(p_{n+1}) - \psi(p_n)$$ where $p_n$ is the $n$-th prime, and $\psi(x)$ second Chebyshev function. With $u=\log(x)/\log(2)$, This the same as, with the first Chebyshev function ...
6
votes
1answer
461 views

Supposed proof of dirichlets theorem on primes

I think theirs somthing wrong with this proof as it was not hard to create, if someone could find a mistake I would greatly appreiciate it: Define a function $[k\equiv b \bmod a]$, to be equal to ...