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
0answers
5 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
18 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
40 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' ...
6
votes
1answer
78 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
20 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
21 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
72 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 ...
1
vote
0answers
23 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
29 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
18 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
61 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 ...
1
vote
0answers
87 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
109 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.
22
votes
2answers
343 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
60 views

Logic puzzle of two numbers

The puzzle goes like this.. ...
0
votes
1answer
65 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
28 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
37 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 ...
1
vote
1answer
17 views

Prove that if $p\le n$, then $p$ does not divide $n! + 1$

I'm having trouble on how to approach this problem Prove that if $p\le n$, then $p$ does not divide $n! + 1$ ($p$ is prime and $n$ is an integer).
1
vote
2answers
56 views

Primes of the form $an^2+bn+c$?

Wondering if this has been proven or disproven. Given: $a,b,c$ integers $a$, $b$, and $c$ coprime $a+b$ and $c$ not both even $b^2$-$4ac$ not a perfect square are there infinite primes of the ...
1
vote
0answers
24 views

Composite residuosity statement.

Consider the following definition. A number $z$ is said to be $n$-th residue modulo $n^2$ , if there exists a number $y \in \mathbb{Z}_{n^2}^*$ such that $$z\equiv y^n \mod n^2$$ Let us take $n=6$ ...
0
votes
0answers
36 views

Proof of Gauss formula to find number of Primes

How did gauss found this formula to find the number of primes when he was 15 , can anyone provide me the proof.
1
vote
1answer
30 views

Fermat's little theorem question

I'm studying Number theory (in my spare time) and I need to prove a lemma in order to prove the exercise. The topic is Fermat's little theorem. Well the lemma goes like this: Let's say we have ...
2
votes
1answer
60 views

On Properties of Exponentially Prime Numbers

A usual prime number is a number greater than $1$ which is not in the form of multiplication of two numbers greater than $1$. We may consider the following natural generalizations: $p>1$ is $+$ - ...
-1
votes
1answer
27 views

Prove that the sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. [closed]

Prove that the Sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. I don't know where to start and how to strictly prove this statement.
14
votes
2answers
198 views
+50

An interesting table of Prime Generating polynomials similar to $n^2+n+41$?

Here is some data on quadratic prime generating polynomials of a particular form. Kindly look at the questions given below it. $$\begin{array}{cccc} \text{#} & P(n)=an^2+bn+c\,; & d = ...
2
votes
0answers
27 views

Proof without using the proof of contradiction

By using the proof by contradiction I can determine that the root of a prime number is irrational. But how can I proof this by using the rational roots test to find rational factors of $x^n - p$. How ...
2
votes
2answers
17 views

If $n>1$ has $r$ different prime factors, then the totient is bounded by $\varphi(n) \geqslant n/2^r$?

I want to prove that if $n>1$ has $r$ different prime factors, then $$\varphi(n) \geqslant \frac{n}{2^r}.$$
0
votes
0answers
14 views

Counterexample to a generalization of Gilbreath's conjecture

Consider the arrays with "initial conditions" $L_1^1>0,\ L_{n+1}^1>L_n^1,\ L_1^{i+1}=1$ satisfying the recurrence $L_n^{i+1}\in\{L_n^i-L_{\large{\inf\{m\in\Bbb Z_{>n}:L_m^i\leq ...
0
votes
1answer
33 views

Proving $\lambda$ is the smallest one possible.

From this question , its proved that for all co-primes $a$ of $n(=pq)$ , $a^\lambda \equiv 1 \mod n$ where $\lambda= lcm (p-1,q-1)$ But how to prove that it is the smallest one possible . My ...
2
votes
1answer
30 views

Closed-form of prime zeta values

The prime zeta function is defined as $$P(s)=\sum_{p\,\in\mathrm{\mathcal P}} \frac{1}{p^s},$$ where $\mathcal P$ is the set of prime numbers. It converges for all $\Re(s)>1$. There is a related ...
0
votes
1answer
80 views

Numerical value of $\sum_{p \in \mathcal P} \frac1{p\ln p}$

In this question we determine that the series $\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges, where the sum runs over primes. As I see the convergence is really slow. The partial sums for given ...
0
votes
0answers
52 views

Divisibility lattice and duality with topological spaces

Consider the integers $\mathbb{N}$ seen as a poset with divisibility as an order relation. See it as a distributive bounded lattice with gcd and lcm, with gcd being the meet and lcm the join. Clearly, ...
4
votes
2answers
167 views
+50

$\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges or diverges?

We will denote the set of prime numbers with $\mathcal P$. We know that the sum $\sum_{n=1}^{\infty}\frac1n$ and $\sum_{n=2}^{\infty}\frac1{n\ln n}$ diverges. It is also known that $\sum_{p \in ...
0
votes
0answers
29 views

Koch's version of the Riemann hypothesis for $x=p^2$

According to von Koch 1991, if the Riemann hypothesis is true, then the for the prime counting function $$\pi(x)=Li(x)+O(\sqrt x \log x)$$ For this equation, does there exist any reference or does ...
2
votes
3answers
64 views

Is this formula: $81n^2+135n+97$ wealth by prime numbers which n is natural number?

I made some effort to set a wealth quadratic formuala for prime, I found this formula: $A(n)= 81n^2+135n+97$, it gives primes for $n=0 $ to $n=18 $. I would be like some one to show me if this ...
0
votes
2answers
26 views

Proof with multinomial.

Let $p$ be a prime number. Prove that $p$ divides the multinomial $$\binom {p}{n_1,n_2,\dots, n_k}$$ such that $n_i \neq p$. I tried some approaches but honestly i have no idea what to do.
0
votes
0answers
23 views

Strong pseudoprime base b

Show that the composite number 1281 is a strong pseudoprime base 41. "$n-1=2^rm$, then n is a strong pseudoprime base b if either $b^m=1modn$ or $b^{2^sm}=-1modn$" Ok so I have $n=1281$ and $b=41$ ...
0
votes
1answer
46 views

Proof, that $a \equiv 1 \pmod{p}$

Let $n \in \mathbb{N}^{+} \smallsetminus \{{1}\}$ and $p = min\{p \in \mathbb{P} : p \mid n\}$. Also, let $a \in \mathbb{Z}$ and $a^n \equiv 1 \pmod{n}$ I need to proof, that $a \equiv 1 \pmod{p}$. ...
1
vote
0answers
42 views

How many unique combinations of sets can we get?

Starting with $x$, which is a positive integer or zero, and $y$ a second positive integer or zero, with $y \ne x$, we can create lists. Set $p$ a prime greater than 2, $\alpha = (p-1)/2$, and ...
2
votes
3answers
38 views

Quadratic that yields the longest prime sequence?

The quadratic $n^2+n+41$ yields prime numbers all the way up to $n=40$ before it fails (pretty cool!). My question is: Do you know of a quadratic that can 'last even longer'?
0
votes
2answers
47 views

Division algorithm and Prime Numbers

In my class, the professor went through a proof that if $p|xy$ then $p|x$ or $p|y$. where p is a prime number. And now that I am reading through it, there is a small piece of the proof that I do not ...
2
votes
2answers
39 views

Total possible combinations of primes

I have been working on a problem as follows: Do there exist 100 consecutive natural numbers none of which is prime? I know that the answer is 'yes', by considering 101!, and noting the sequence 101! + ...
12
votes
0answers
134 views

Sheldon Cooper Primes

On the $73^{\text{rd}}$ episode of the Big Bang Theory, Dr. Sheldon Cooper, an astrophysicist portrayed by Jim Parsons $(1973 - \stackrel{\text{hopefully}}{2073})$ revealed his favorite number to be ...
3
votes
2answers
101 views

Is there always a prime between $n$ and $2n$?

if we are interested to seek for the numbers of primes between $1-100$ and $100-1000$ or 1000..., why we don't asked if there is a always a prime between $n$ and $2n$ mayeb this interesting question ...
0
votes
1answer
30 views

Is $f(n)= \sum_{1\leq i \leq n}\log(i) - \sum_{\text{p is prime},\ p\leq n} \log(p)^2$ a function of $\operatorname{O}(n^{\frac{1}{2}+\epsilon})$?

Is $$f(n)= \sum_{1\leq i \leq n}\log(i) - \sum_{\text{p is prime},\ p\leq n} \log(p)^2$$ a function of $\operatorname{O}(n^{\frac{1}{2}+\epsilon})$? if no, what do we know about its asymptotic ...
0
votes
2answers
31 views

$R$ integral domain : $u\in R^*, a \text{ is prime} \iff au \text{ is prime}$

$R$ integral domain : $u\in R^*,\; a \text{ is prime} \iff au \text{ is prime}$ I started by looking at $auu^{-1}$. What should I do next? I'd be glad for help. Note: $u \in R^*$ meaning is $u$ ...
4
votes
1answer
34 views

Proving that an ideal is prime - is it correct?

I need to prove that although $X^2 + 3X +1 \in \mathbb{Z} [X]$ is irreducible, the ideals $(5,X^2 + 3X +1 )$ and $(11, X^2 + 3X +1)$ are not prime. I know that an ideal $I$ is prime iff ...
3
votes
1answer
61 views

$p^3 + 2$ is prime if $p$ and $p^2 + 2$ are prime?

I'm self-learning number theory. I want to prove the following statement: $$p \text{ is prime } \land \text{ }p^2 + 2 \text{ is prime } \implies p^3 + 2 \text{ is prime }$$ I failed to do so, and I ...
0
votes
0answers
10 views

Least upper bound for $k$ such that $kp+r$ is a prime but with different binary length.

If $p$ is a prime number then is there any upper bound for $k$ (say $U$) such that $kp+r$ is also prime where $k$ is a positive integer , and $r$ is a non-negative integer lies between 0 and $p-1$ but ...