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

5
votes
2answers
59 views

Prove or disprove that $p_n > e^{p_n - p_{n-1}}$ for large enough $n$.

Let $p_n$ denote the $n$-th prime. Prove or disprove that for large enough $n$ we have $$p_n > e^{p_n - p_{n-1}}.$$ The inequality trivially holds for all the twin primes larger than $7$. With ...
6
votes
1answer
165 views

How can I know if $2^{2^{2^{2^{2}}}}+1=?$ is prime?

I could calculate the following prime numbers $$2+1=3$$ $$2^{2}+1=5$$ $$2^{2^{2}}+1=17$$ $$2^{2^{2^{2}}}+1=65537$$ Are the following numbers prime??? $$2^{2^{2^{2^{2}}}}+1=?$$ ...
2
votes
2answers
35 views

In Zagier's one-sentence proof, why is S defined to be {(x,y,z)∈ℕ^3:x^2+4yz=p,p prime}?

I've looked at a very clear explanation of Zagier's proof (specifically, it can be found here:http://danielmath.wordpress.com/2012/12/26/one-sentence-proof/) but the first step still eludes me: why is ...
2
votes
1answer
43 views

Does it have convergent subsequence in that form? [duplicate]

Let $P_i$ be sequence of prime numbers i.e $P_1=2,P_2=3,P_3=5 ...$ Euler has proved that the sum $$\sum_{i=1}^{\infty}\dfrac{1}{P_i}$$ is divergent. Set $a_i=P_{P_i}$ then $a_1=P_2=3$ , ...
0
votes
1answer
37 views

Logical contradiction regarding cardinality of sets - help resolve

Consider the set of all natural numbers, $\mathbb{N}$. This set is composed of two subsets, the set of all primes, we'll call $\mathbb{P}$, and the set of all composite numbers (non-primes), ...
1
vote
4answers
138 views

How can prime numbers be found mentally?

At a careers fair I was given a test to see how good I am at mental maths, And I was given multiple questions, asking whether a number was a prime. Example question: Which of these numbers isn't a ...
1
vote
3answers
58 views

Expressing a number that doesn't exist [closed]

How can one express something like $x \in \pi$ where $\pi$ is a set of prime numbers and $d$ is some divisor such that $\pi = \lbrace n:d|n\rbrace = \lbrace {1, p}\rbrace$? Or should I do something ...
0
votes
1answer
24 views

Number of prime divisors

Is there a way to express all the prime divisors of a natural number x as a function? Thanks in advance.
1
vote
4answers
69 views

I Don't Understand This Proof of Infinitely many Primes

The Proof What Confuses Me I follow the proof up until the point highlighted by the red square. I realize we must have $p_j|a$ (all composite numbers have a prime divisor) but why do we have the ...
3
votes
1answer
57 views

Given a set of powers of two, how “close” can we come to a prime?

Given a natural $n \ge 2$, we can construct a set of all powers of two from $2^n$ to $2^{4n}$: $$\{2^n, 2^{n+1}, 2^{n+2}, \dots, 2^{4n}\}$$ How close does one of these numbers come to a prime in the ...
7
votes
0answers
85 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
2
votes
0answers
33 views

Size of increments in commutative ring to reach given number

I have the ring $\Bbb Z_q = \{0,1,\ldots,q-1\}$, where $q$ is a prime. Starting from $0$, I want to make exactly $n$ equally sized increments and reach $a\in \Bbb Z_q$, with $n<q-1$. For example if ...
2
votes
1answer
66 views

Improvements of Dusart's lower bound for $ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}$.

Let $\gamma$ be the Euler-Mascheroni constant. In this paper (Theorem 6.12) it is proved that for $x\ge 2793$, $$ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}> 1-\frac{1}{5 \left(\log ...
0
votes
3answers
76 views

Isn't this the most compact binary representation of all numbers?

Here is the transformation: $$\begin{align*} &1\to(0)\\ &2\to(1)\\ &3\to(10)\\ &4\to((1))\\ &5\to(100)\\ &6\to(11)\\ &7\to(1000)\\ &8\to((10))\\ &9\to((1)0)\\ ...
0
votes
1answer
18 views

How to negate $(a=1 \text{ and } b=n) \text{ or } (a=n \text{ and } b=1)$ to get $1<a<n \text { and } 1<b<n$?

n>1 is composite if and only if it can be written as a product $n=ab$ of integers $a$ and $b$ such that $1<a<n$ and $1<b<n$. If a prime number $n$ is the product of two positive ...
4
votes
2answers
110 views

Prove that there are infinitely many primes of the form $8k + 3$

Prove that there are infinitely many primes of the form $8k + 3$ I have seen proofs for $4k+1$ and $8k+1$ and $4k+3$ but struggling with this one please help The suggestion given is to consider a ...
8
votes
3answers
268 views

Prime numbers divide an element from a set

Show that if $p$ is a prime number different from 2 and 5, then it divides at least one of the elements of the set $\left \{ 1,11,111,1111,...\right \}$.
2
votes
2answers
113 views

Proving $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$ for prime $p$ [closed]

I am having trouble proving that any prime number $p$ and integers $a$ and $b$, $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$
2
votes
1answer
19 views

Integrating Chebyshev theta function

I'm trying to compute the following integral ($ \vartheta(x) = \sum\limits_{p \leq x}\log(p) $) $$\int\limits_{0}^{\infty}\vartheta(e^x) e^{-(1+s)x} \text{dx}$$ The result is supposed to be $ ...
0
votes
1answer
60 views

Why was 1 considered as prime years ago? [duplicate]

I've seen on Maths Is Fun that years ago, 1 was considered as prime, but now, it is not. How did this happen? I know that a prime number has only two factors, 1 and itself, and we have 1, which is ...
0
votes
1answer
43 views

show that if $2^n -1$ is prime than n is also prime

How to prove the above statement? Do you have to use Fermat's little theorem where $a^p = a (\mod p)$ I cannot see how to use the above here I tried to factorise $2^n -1 = (2-1)(2^{n-1} + 2^{n-2} + ...
1
vote
1answer
24 views

Amount of numbers that are coprime to a Mersenne number

Let $M_p = 2^p-1$ be a Mersenne number, where $p$ is prime. Is it known that almost every number in the interval $[1, M_p]$ is coprime to $M_p$? That is, is it known that $$ \lim_{p \to \infty} ...
0
votes
1answer
27 views

Counting number of elements of prime order.

Let $p$ be prime where $p$ does not divide the order of the group G. Consider these groups: $G\oplus Z_{p^4}; G\oplus Z_{p^3}\oplus Z_p; G\oplus Z_{p^2}\oplus Z_p\oplus Z_p; G\oplus Z_{p}\oplus ...
1
vote
0answers
32 views

prime case function?

Does there exist a name (or assigned to a mathemtician) for a case function $f(x)$ in literature, such that it twould take the value $1$ when $x$ primes, and zero otherwise? I am just looking for a ...
1
vote
3answers
47 views

Probability that a Mersenne number is prime

Let $p$ be a prime and let $M_p = 2^p-1$ be a (Mersenne) number. Is there any known result on the probability that $M_p$ is prime? In particular is it known whether the probability tends to $1$ as $p ...
13
votes
1answer
160 views

Nature of the series $\sum\limits_{n}(g_n/p_n)^\alpha$ with $(p_n)$ primes and $(g_n)$ prime gaps

Let $p_n$ denote the $n$th prime number and $g_n=p_{n+1}-p_n$ the $n$th prime number gap. This is to ask for which values of $\alpha$ the series $S_\alpha$ converges or diverges, where ...
0
votes
1answer
183 views

Is this infinite series related to prime and composite numbers convergent?

I don't know whether this series converges: $$\frac{1}{4} - \frac{1}{5} + \frac{1}{6} - \frac{1}{7} + \frac{1}{8} + \frac{1}{9} + \frac{1}{10} - \frac{3}{11} + \frac{1}{12} - \frac{1}{13} + ...
2
votes
0answers
74 views

Does this formula always yield a prime?

Somehow $\tau=1.2516475977905$ appears to have the property that $$ \left\lfloor 2^{2^{{\,}^{\cdot^{\cdot^{\cdot^{\tau}}}}}}\right\rfloor $$ is always a prime. Here $\lfloor x\rfloor$ denotes the ...
0
votes
3answers
26 views

Nonzero quadratic residues modulo 101

How many Nonzero quadratic residues are there modulo prime 101 I am lost where to start to my knowledge there is no formula for number of quadratic residues a prime has It will be too much to start ...
0
votes
1answer
44 views

How to prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$?

Let $$\omega(n) := \text{number of distinct primes dividing } n. $$ How can one prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$? I know that $\omega(n)! \leq ...
2
votes
1answer
66 views

Sequences for that $\sum_{n} \frac{1}{x_n}$ is divergent and $\sum_{n} \frac{1}{x_n \ln x_n}$ is convergent

We will denote with $(x_n)$ a given sequence and we introduce the following two series. $$S^* = \sum_{n} \frac{1}{x_n} \quad \text{and} \quad S_* = \sum_{n} \frac{1}{x_n \ln x_n}.$$ We know that if ...
2
votes
1answer
18 views

Question about coprime intergers a,b that satisfy sa+tb=n for positive s and t.

Let a,b be coprime positive integers, find an integer N (depending on a and b), such that for any integer n > N it is possible to find integers s, t ≥ 0 satisfying sa+tb = n, but no such s, t exist ...
0
votes
1answer
26 views

How to answer the following question regarding a certain number of primes in a certain interval?

For an analytic number theory homework assignment, we are asked to prove the following (using the Prime number theorem $\pi(x) \sim x/\log(x)$ as $x \to \infty$ ): For every $\epsilon > 0 $ and ...
2
votes
0answers
24 views

Largest prime factor of a Mersenne number with exactly two prime divisors

For a prime $p$, let $M_p = 2^p-1$ be a (Mersenne) number with exactly two prime divisors, and let $P(p)$ be the largest of these two. Clearly $P(p) > \sqrt{M_p}$. This is very likely a hard ...
2
votes
1answer
61 views

What are the connections between the three Mertens' theorem?

In number theory the three Mertens' theorems are the following. Mertens' $1$st theorem. For all $n\geq2$ $$\left\lvert\sum_{p\leqslant n} \frac{\ln p}{p} - \ln n\right\rvert \leq 2.$$ Mertens' ...
7
votes
1answer
100 views

Probability of an integer being a prime

$\Omega=\mathbb{N}^*,P(\omega=n)=\dfrac{1}{2^n}$, let $A_k$ be the event $k\mid\omega$. 1) Find $P(A_k)$ 2) Let B be the event "$\omega$ is prime", show that ...
0
votes
0answers
23 views

big $\mathcal O$ for number of prime in an interval?

According to von Koch 1991, if the Riemann hypothesis is true, then the for the prime counting function $$\pi(x)=Li(x)+\mathcal O(\sqrt x \log x)$$ I am trying to understand how to deal with the ...
1
vote
1answer
24 views

Conjecture on the value of limit and related primality testing

Just I made a curious conjecture when I was playing with my calculator. We will use $\displaystyle\prod_{i=1}^n p_i$ where $p_i$ is the $i$-th prime. Then I have noted that, $$\left\lvert\cos ...
5
votes
1answer
84 views

Being $N$ a constant $>0$, show $\prod_{p<x}_{p \ \text{prime}}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}$.

Related. Show that if $x$ is large enough,$$\prod_{p<x}_{p \ \text{prime}}\frac{1}{p^{N+1}-1}>\frac{0.2}{\log^2 x}.$$ Speaking of which, Theorem 6.12, and maybe others, of this paper might be ...
2
votes
0answers
28 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 ...
4
votes
1answer
41 views

Do primes modulo k form a normal sequence?

For some $k>2$, form a sequence whose nth term is the nth prime that is not a divisor of $k$ modulo $k$. e.g. for $k=4$ the sequence would be 1,3,1,3,3,1,1,3,3,1,3,1... Is this sequence normal, ...
0
votes
1answer
19 views

Prove that $\Bbb F_p^\times$ is equal to Miller–Rabin primality test for prime number

I want to prove, that $\Bbb F_p^\times = MRP(p)$. I think, that I have to start with this statement: $\{a \in \Bbb F_p^\times | a^2 = 1 \} = \{1; -1\}$ But I do not know how to continue this idea.
2
votes
1answer
66 views

Finding the least prime of the form $6^{6^6}+k$

I try to find the least prime number of the form $6^{6^6}+k$. I sieved out the candidates by trial division upto $10^6$, but there are still many candidates left upto $k=10000$ How can I further ...
2
votes
1answer
127 views

Is $\frac{1}{e^\gamma\log x} \prod\limits_{p < x,p\,\text{prime}} \frac{p}{p-1}<1+ \prod\limits_{p<x,p\,\text{prime}}\frac{1}{p^{n+1}-1}?$

Let $n$ be an initially arbitrarily large variable, but always decreasing (and more specifically non-increasing) to exactly $1$ when $p$ is the largest prime in the product. Then, denoting with ...
2
votes
2answers
114 views

A Proof for Prime Numbers

Show that among k-digit numbers, one in about every 2.3k is a prime. How can we prove this question? Thanks.
35
votes
1answer
787 views

Estimate for $n$th prime

A good approximation I have found for $p_{n}$ is \begin{align} \int_{2}^{n}\log (x \log (x \log (x)))\ dx\\ \end{align} and seems to be a better estimate than $n \log (n)$. The error term seems to ...
0
votes
0answers
74 views

Logic puzzle of two numbers

The puzzle goes like this.. ...
0
votes
1answer
68 views

prime number greater than 100

I 'm confused about prime number. It is possible that we can find a not prime number that is greater than 100 and not divided by {2,3,5,7,9}. because someone said to me that we can check if a ...
1
vote
1answer
29 views

Solutions of $a^{2} - 2b^{2} \equiv 0$ mod $p$

I came across this question in attempting to find $p$ for which $\mathbb{Z}_{p}[\sqrt{2}]$ is a field. Consider the equation: $$a^2 - 2b^2 \equiv 0 \enspace \text{mod p}$$ For which primes $p$ is ...
1
vote
2answers
53 views

for all positive integers m there exists consecutive primes which are at least m apart

I'm having difficulty as to how I should approach this problem, any help would me much appreciated! Note that $k$ divides $n! + k$ for each $k\le n$. Use this fact to show that for all positive ...