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

37
votes
7answers
25k views

Is there a known mathematical equation to find the nth prime?

I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
2
votes
3answers
100 views

Can this function be a new test for primality?

The following function returns always 0 only if a number is not prime. $$ H(x)=\prod_{i=2}^{x-1}\left\{\left[\sum_{k=1}^{x/i}(-i)\right]+x\right\} $$ what do you think? Bye!
5
votes
1answer
66 views

the least prime leaving prime remainder when divided by 2,3,5,…

What is the least prime giving a prime remainder when divided by 3? It is 5. What is the least prime giving prime remainders for both 3 and 5? It is 17. For division by 3,5,7 it is also 17. For ...
1
vote
0answers
14 views

It is possible to find the exact value of prime number without approximation ( PNT)? For instance I want to know how many primes are below 8111.

It is possible to find the exact value of prime number without approximation ( PNT)? For instance I want to know how many primes are below 8111 or any value of N.
1
vote
2answers
31 views

Testing prime numbers with modified Fermat's Little Theorem

Is there a number $n$ such that: $6n-1$ is prime There exists a positive integer $r<3n-1$ such that $4^{r}\equiv1\pmod{6n-1}$
0
votes
1answer
20 views

Using the prime number theorem to find a continuous function mapping primes?

The prime number theorem gives an increasingly (proportionally) accurate approximation for the number of primes below $x$. Can we use this to find an equivalently accurate approximation which maps the ...
3
votes
0answers
17 views

$\sup\left(\frac{\log(\mbox{ lcm }(1,2,\ldots,k))}{k}\right)$ for $k\in \Bbb{Z}, k>1$

In a previous question Asymptotic growth of l.c.m. of all integers below $k$, it was noted that using the Prime Number Theorem you can prove that $$ \log(\mbox{ lcm }(1,2,\ldots,k)) =k+\mbox{ o}(k)$$ ...
11
votes
1answer
196 views

Are there infinitely many pairs of primes where each divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
-2
votes
0answers
28 views

Any prime number $(p)$, in sequence $(p^n, p^n+1…)$. Each term in sequence is divisible only for previous terms? [on hold]

Any prime number $(p)$, in sequence $(p^n, p^n+1...)$. Each term in sequence is divisible only for previous terms? This é relevant or simple derivation?
1
vote
1answer
86 views

Can composite numbers be uniquely written as a sum of two squares?

Let $X = a^2 +b^2$ where all the terms are positive integers and $X$ is a composite number and $\gcd(a,b)=1$ . Do there exist positive integers $c$ and $d$ other than $a$ and $b$ such that $X = c^2+d^...
1
vote
1answer
24 views

Lemma Using Proth's Theorem ${(a, a+1)}^{(p-1)/2}$ $=$ $-1$ $\pmod p$ and $p$ is composite?

Proth's Theorem: Let $p=k*2^n + 1$ where $k$ $<$ $2^n$. If there is any integer $a$ such that $a^{(p-1)/2}$ $=$ $-1$ $\pmod p$, then $p$ is prime. Can anyone please find a counterexample (...
0
votes
2answers
75 views

Primality testing though trial division.

I am having difficulty to understand this statement mentioned here: Remember that any composite integer n is build out of two or more primes n = P * P … P is largest when n has exactly two ...
6
votes
4answers
159 views

Disprove that “if $p$ is a prime number, then $2^p-1$ is also a prime number”?

We can see manually that $2^p-1$ is not prime. As $2047$ is not a prime. $2^{11} = 2048$. But I'm unable to figure out a formal way of disproving the statement.
2
votes
4answers
258 views

The Frobenius Coin Problem

I am asked to prove that: For integers $n, x,y > 0$, where $x,y$ are relatively prime, every $n \ge (x-1) (y-1)$ can be expressed as $xa + yb$, for $a,b \ge0$. How should I approach ...
19
votes
6answers
5k 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 ...
1
vote
0answers
44 views

Can “sufficiently large” be made more concrete?

Here https://en.wikipedia.org/wiki/Prime_gap an observation of Chudakov is mentioned : For every $\theta>\frac{3}{4}$ there exists an $N$ such that $g_n<p_n^{\theta}$ for all $n\ge N$. ...
2
votes
0answers
77 views

Even natural numbers are sums of two primes with twins or of two primes without twins

I seems to be very few even numbers that can't be written as a sum of two primes with twins or as a sum of two primes without twins. That is, suppose that $\mathbb P'$ is the set of the primes not ...
6
votes
2answers
60 views

$a_n$ is relatively prime to $a_k$ for $k<n$

Let the sequence $\{a_n\}_{n=0}^\infty$ be defined by $a_n=|n(n+1)-19|$. Show that for $n\neq 4$, if $a_n$ is relatively prime to $a_k$ for all $k<n$, then $a_n$ is prime. The first few terms are $...
2
votes
1answer
38 views

Small primes congruent to $a$ mod $p$.

Let $p$ be a prime and $a$ be an integer such that $0 \lt a \lt p$. Is there a prime number, $q$, congruent to $a$ mod $p$ such that $q\lt p^2$? I have checked that this is true for the first $3000$...
2
votes
1answer
16 views

Euclid Mullin Sequence

Consider the Sequence as follows. Let $a_1 = 2$, $a_n$ be the largest prime divisor of $P_n = 1 + {\prod_{i = 1}^{n - 1} a_{i}} $ Then we obtain a sequence of prime numbers How do you show that 5 ...
1
vote
1answer
40 views

Examples of Weil's explicit formula

In Bombieri, PROBLEMS OF THE MILLENNIUM: THE RIEMANN HYPOTHESIS, Clay Mathematics Institute (2000), from page 8, V. Further evidence: the explicit formula the author tell us that there is a ...
5
votes
2answers
59 views

Which primes $p$ divide $q^q-1$ for a prime divisor $q$ of $p-1$

I am looking for (a formula) for all the primes $p$ less than or equal to $X$ with the following criteria: There is at least one prime $q$ dividing $p-1$ such that $p$ divides $q^q-1$. $7$, for ...
2
votes
1answer
43 views

For each prime $p>3$ there are non twin primes $q,r$ with $p^3=2q+r$

Define $\mathbb P'=\{n\in\mathbb P|n-2,n+2\notin \mathbb P\}$. Conjecture: Given a prime $p>3$, then $\exists q,r\in\mathbb P':p^3=2q+r.$ Tested for the first 10000 primes. The solutions ...
3
votes
1answer
20 views

Maximum length of a string that has no substring divisible by a prime number $p$ is $p-1$?

What is the maximum length of a string of nonzero digits that has no substring that is divisible by a given prime number? I want to find a string of length n which has no substring divisible by the ...
3
votes
1answer
93 views

multiples (of primes) coverage formula

I apologize in advance if my explanation is not clear. Please let me know if clarification is required and I will do my best to fix it! I am attempting to find an explicit formula (in terms of ...
9
votes
1answer
117 views

Conjecture: Every prime number is the difference between a prime number and a power of $2$

Conjecture: $\forall p\in\mathbb P\exists q\in\mathbb P\exists n\in \mathbb N: q-p=2^n$ Verified for the 100 first primes.
3
votes
5answers
246 views

A statement about divisibility of relatively prime integers

I'm solving a problem, and the solution makes the following statement: "The common difference of the arithmetic sequence 106, 116, 126, ..., 996 is relatively prime to 3. Therefore, given any three ...
1
vote
2answers
37 views

Dirichlet inverse of $(-1)^n$

I was tinkering around and noticed the Dirichlet inverse of $\,f(n) = (-1)^n$ seems to be $$ f^{-1}(n) = -\mu\!\left(n\,/\,2^{\nu_2(n)}\right)\left\lceil 2^{\nu_2(n)-1} \right\rceil, $$ where $\nu_p(n)...
4
votes
2answers
63 views

Growth of $\pi(2x) - 2\pi(x)$

In Hardy & Wright's Theory of Numbers (p. 494f in 6th ed.) there's a little discussion following the proof of the prime number theorem. We have $$ \pi(2x) - \pi(x) = \frac{x}{\log x} + o\...
31
votes
7answers
5k views

How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4?

It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian ...
5
votes
1answer
46 views

Are the extremas of $h(x)$ global?

It is well known that $li(x)$, the integral logarithm is a very good approximation of $\pi(x)$, the nunmber of primes not exceeding $x$. So, a very good approximation for the probability, that a ...
4
votes
1answer
64 views

What is the computational complexity of calculating $\pi(x)$ exactly?

The prime counting function $\pi(x)$ has been determined for $x=10^{26}$. The list of the $10^n$-th primes , however , ends at $n=18$. The $10^{18}$-th prime has $20$ digits. Apparantly, the ...
25
votes
1answer
874 views

Primes approximated by eigenvalues?

Consider the infinite matrix starting: $$\displaystyle T = -\left( \begin{array}{ccccccc} +1&+1&+1&+1&+1&+1&+1&\cdots \\ +1&-1&+1&-1&+1&-1&+1 \\...
1
vote
0answers
27 views

Division/Remain by a Mersenne Prime

Is it possible to compute the integer division and remainder of an integer $x$ by a Mersenne prime $p$ using only bitwise operations?
14
votes
1answer
715 views

How many digits of the googol-th prime can we calculate (or were calculated)?

Here, a lower and upper bound for the $n$-th prime are given. Applying the given bounds $$n(\ln(n\cdot\ln(n))-1)<p_n<n\cdot\ln(n\cdot\ln(n))$$ and the approximation $$p_n\approx n(\ln(n\...
2
votes
1answer
41 views

Primes that are neither twin, cousin or sexy [on hold]

I'm reading up on prime pairs, and I had a question... I can't seem to find an answer to this anywhere, and the wikipedia list of prime types is enormous! Afraid I missed it when going through it. I ...
4
votes
2answers
61 views

Why can the sieve of eratosthenes not be used to confirm the twin primes conjecture?

I have been having fun thinking about sieves and more particularly the twin prime conjecture. As I am fairly new to this type of mathematics, I am wondering, if we use the sieve of erastothenes, aka ...
1
vote
1answer
55 views

Strange results in mersenne.org database

I am interested in GIMPS project. I was browsing through known Mersenne prime numbers when I discovered strange records in their database. For example, M6972593 is the 38th Mersenne prime. However, ...
1
vote
0answers
11 views

Is there a way to translate the Sacks Spiral into a triangle?

The sacks spiral is our natural number system written in the form of a spiral and it highlights the primes which seem to fall on certain curves within the spiral. I am interested to know if there is a ...
3
votes
0answers
58 views

A function can provide the complete set of Euler primes via a Mill's-like constant. Is it useful or just a curiosity?

The following $f(m,n)$ function provides the complete set of Euler primes (OEIS A196230): $$f(m,n)=m^2-m+[\lfloor E^{2^n} \rfloor - {\lfloor E^{2^{n-1}} \rfloor}^2 +\frac{\lvert n-(\frac{1}{2}) \...
1
vote
0answers
29 views

Generalization of Mill's theorem

Mill's theorem states that there exists a positive real number A such that the floor of the double exponential function $A^{3^n}$ are primes for all positive integers n. The value of A is ...
0
votes
0answers
58 views

A conjecture relating to Goldbach

I have a conjecture related to the strong Goldbach conjecture and the Goldbach function. It is that: for any $g(E)$, there are a finite number of even numbers which can be expressed as a sum of two ...
1
vote
2answers
117 views

Primes in the binomial transform of $ [1, 1, 2, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, …]$.

This question is related to this sequence A139482. A commentator gives the following formula for $a_m$ $$a_m = {3m^2-9m+10 \above 1.5pt 2}$$ I have that you should consider the sequence $b_n =3n+2$ ...
7
votes
3answers
54 views

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$.

Prove that $\sum^{n-1}_{i=1}i^{(n-1)} \equiv -1$ (mod $n$) for all prime $n\in\mathbb{N}$. I'm having a difficult time proving this problem. I was able to verify that it works for prime $n$ up to ...
30
votes
7answers
3k views

Can a complex number be prime?

I've been pondering over this question since a very long time. If a complex number can be prime then which parts of the complex number needs to be prime for the whole complex number to be prime.
0
votes
0answers
37 views

Can do you repeat these calculations combining the explicit formula and Nicolas criterion, on assumption of the Riemann Hypothesis?

I did easy calculations to get for $x=N_k=\prod_{n=1}^k p_k$ the kth primorial, combining the so-called explicit formula$\dagger$ for the second Chebyshev function and Nicolas criterion for the ...
2
votes
3answers
67 views

$p\in\mathbb P\iff\Big(2\leq k<\sqrt p\implies\gcd(k^2,p-k^2)=1\Big ),\;p>3$

This is sharper variant of A condition for being a prime: $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$ It seems enough to test that for some sums: $p=m+n\implies\gcd(m,n)=1$, namely ...
3
votes
1answer
23 views

Common generator of units in finite prime fields

It is well known that the unit group of a finite field is cyclic. What can we say about the generators? Specifically I am interested in the following question: Suppose we fix a positive integer $a$, ...
3
votes
2answers
39 views

Prove or refute that $\{p^{1/p}\}_{p\text{ prime}}$ to be equidistributed in $\mathbb{R}/\mathbb{Z}$

I've tried follow the Example 3 (see minute 30'40" of the reference), where is required the related Theorem (stated at minute 21') combined with Serre's formalism for $\mathbb{R}/\mathbb{Z}$ (also ...
11
votes
2answers
190 views

Two randomly chosen coprime integers

This is a twist on the problem commonly known to have solution $6/\pi^2$. Suppose when choosing from all natural numbers $\mathbb{N}$, the probability of choosing $n \in \mathbb{N}$ is given by $P(n)=...