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

1
vote
0answers
8 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 ...
3
votes
1answer
16 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
16 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
55 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 ...
0
votes
1answer
50 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
59 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.
21
votes
2answers
249 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
54 views

Logic puzzle of two numbers

The puzzle goes like this.. ...
0
votes
1answer
60 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
26 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
33 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
23 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
59 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
26 views

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

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.
12
votes
0answers
138 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
79 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
50 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
136 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
28 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
63 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}$. ...
0
votes
0answers
40 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
127 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
33 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 ...
4
votes
0answers
39 views

Question about primes of polynomial type.

It is well known that $50$ % of the primes are of the form $x^2 + y^2$. Many variants exists where a rational amount of primes is of some integer polynomial form. But I wonder ; are there integer ...
2
votes
0answers
64 views

A similar, but hopefully easier problem than Gilbreath's conjecture

Gilbreath's conjecture says that for every positive integer $n$, if we write out the first $n$ primes $2,3,5,7,11,13,\ldots,p_n$ take the differences between consecutive terms ...
5
votes
1answer
153 views

Does this sequence of sets eventually contain all primes?

I was on Reddit earlier and answered a question about the usual proof that there are infinitely many primes: multiply any finite set of them, add 1, factor, and you get factors that are not in the ...
4
votes
1answer
25 views

Is there an $n$ such that $p|n^2+1$ with $2n<p<2n+\sqrt n$?

Is there an integer $n$ such that $n^2+1$ is divisible by a prime $p$ with $2n<p<2n+\sqrt n$? It's complicated to describe my interest, but these are near-missed for arc-cotangent reducible ...
1
vote
0answers
45 views

Golbach's partitions: is there always one common prime in G(n) and G(n+6) , n greater or equal to 8 (or a counterexample)?

I am trying to find a counterexample for the following expression when d=6. (G(n) = Goldbach partition of the even number n) ${\forall}$ n=2*k / k${\in}$N, n${\geq}$8 ${\exists}$(${p_i}$,${p_j}$) / ...
7
votes
2answers
69 views

$\varphi(N)>\pi(N)$?

Is it trivial that $\varphi(N)>\pi(N)$ for sufficiently big integers $N$, where $\varphi$ is Euler's totient function and $\pi$ is the prime-counting function? The only exceptions less than ...
2
votes
0answers
71 views

Prime Factor Problem To Solve

For any positive integer $n>10$, $\lfloor \sqrt{n!}\rfloor$ has always a prime factor $> n$.