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

2
votes
0answers
158 views

Interchanging limits with the prime counting function

How does one justify that $$\lim_{s \to 1} \lim_{x \to \infty} \frac{\pi(x)}{x^s} = \lim_{x \to \infty} \lim_{s \to 1} \frac{\pi(x)}{x^s}, \quad s > 1,$$ without using the fact that the primes have ...
1
vote
1answer
44 views

Extending $f(p^k)$ where $p$ is prime

If we have a function $f(x)$, for which we know that $f(p^k)=(p^s+1)^k p^{sk}$ where $p$ is prime, $k$ is a real number, and $s$ is a constant, how do we find $f(x)$? My try: let $k=\log_p(x)$, so ...
30
votes
1answer
508 views

Very tight prime bounds

Is it possible that $$\left|\operatorname{li}(n)-\sum_{k=1}^{\lfloor\log(n)\rfloor}\dfrac{\pi(n^{1/k})}{k}-\log(2)-\dfrac{1}{2}\right|<\dfrac{2\sqrt{n}}{e\log(n)}?$$ Since $$ ...
0
votes
2answers
47 views

What is the mean prime power?

I found this definition in a book and I did not understand the meaning of it There exists a field of order q if and only if q is a prime power (i.e., $q = p^r$]) with p prime and r ∈ N. Moreover, if q ...
0
votes
1answer
195 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
3
votes
2answers
125 views

$n^2-79n+1601$ always a prime?

I am struggling with proving or disproving this: $n^2-79n+1601$ is a prime for all natural numbers $n$ (except multiples of $1601$). This somehow has a relation to Stanislaw Ulam spiral. What ...
0
votes
1answer
82 views

Given a prime p and an integer N, find the number of integers n such that 1≤n≤N and order(n!) is divisible by p

We are given a prime number $\leq 10^{18}$ and an integer N $(\leq N\leq 10^{18})$ how to find the number of integers lying in the range $1\leq n\leq N$ for which the order(n!) is a multiple of p? ...
1
vote
1answer
45 views

What's the best software for primality tests of huge numbers? (check if an integer is prime or not)

I just read an article about huge prime numbers (some with more than 10millions digits!) that are discovered using software that check if an integer is prime or not (primality test sofwares). What is ...
4
votes
2answers
48 views

Density in $\mathbb{R}_{ +}$ of a subgroup of $\mathbb{Q}_{> 0}$?

Let $\phi : \mathbb{Q}_{>0} \to \mathbb{Z}$ be the group morphism defined by $\phi(p) = p$ for $p$ a prime number. It follows that $\phi(1)=0$, $\phi(a.b) = \phi(a)+\phi(b)$, $\phi(a^{-1}) = ...
1
vote
1answer
65 views

Is there a prime between $k$ and $\dfrac{11}{9}k$, $\forall k\ge 24$?

Given $k\in\mathbb{N}$, $k\ge 24$, is there always a prime number in the interval $\left[k,\dfrac{11}{9}k\right]$? I tried to verify this statement with the computer and it seems to hold. Is it ...
10
votes
2answers
1k views

Do 4 consecutive primes always form a polygon?

Related to this question, if 4 segments have length of 4 consecutive primes, can they always form a 4-vertex polygon? This question occurred to me out of sheer curiosity, but now I can't prove or ...
1
vote
1answer
66 views

Characterizing the primes which don't divide any Pell-Lucas number(s)

For integer $n$, let $P_n$ be a Pell number, and $Q_n$ its companion. Is there a characterization of the prime numbers $p$ which don't divide any $Q_n$? By brute-force search, I found that this ...
1
vote
0answers
31 views

RSA aloghorithm - stuck on d

I'm sorry in advance if this sort of question has been posted before. I couldn't find it. I'm clearly an idiot, and I clearly need help, so here I am. I have a homework assignment which overall is ...
0
votes
0answers
14 views

Semiprime error margin

As an extension to this question, the plot below shows $$\pi(x)-R(x)\ \ \text{ (blue)},$$ $$\pi_{(2)}(x)-smoothed\left[ ...
2
votes
0answers
35 views

Semiprime asymptotic step function

Since $$\pi_{(2)}(x)=\sum_{i=1}^{\pi(x^{1/2})}\left(\pi\left(\dfrac{x}{\text{p}_i}\right)-i+1\right),$$ where $\pi_{(2)}(x)$ denotes the semiprimes and $\text{P}_i$ is the $i$th prime, an asymptotic ...
9
votes
2answers
121 views

Sets of Prime Numbers Generated By an Irreducible Monic Polynomial

Given a non-constant integral irreducible monic polynomial $f(x)$, the prime factors of its value at integers $x\in\mathbb{N}$ forms a set $\mathcal{P}(f)$. Is it possible that ...
3
votes
1answer
87 views

Probability that two random integers have only one prime factor in common

The probability that two integers picked at random are relatively prime is known to be $1/\zeta{(2)}=6/\pi^2\approx0.607927...$. Generalizing, the probability that $n$ random integers have $\gcd=1$ is ...
0
votes
0answers
102 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ ...
2
votes
0answers
58 views

totally split primes in a number field

I have to show: For any number field $K$, there are infinitely many prime numbers $p \in \mathbb{N}$, that are totally split in $K$. I think have already shown (with some hints my professor gave) ...
3
votes
1answer
158 views

An integral and $\pi(n)$

Are there polynomials $P,Q\in \mathbb{R}[x]$ satisfying : $$\int_{0}^{\log n}\frac{P(x)}{Q(x)}\,\mathrm{d}x=\frac{n}{\pi(n)}\quad \text{ for infinitely many }n\in \mathbb{N}$$ Here $\pi(n)$ is the ...
3
votes
3answers
135 views

Number of primes less then $6000$ using $n/ \log n$

So I am trying to use this formula here and is giving me some trouble. If I just substitute $6000$ into the formula, the answer is approximately $1500$. But the number of primes under $6000$ is ...
2
votes
1answer
83 views

Infinite families of prime numbers

What interesting/useful infinite families of prime numbers are there? Right now it would be useful if I could find one with arbitrarily many 1's in its binary representation, but I am doing a larger ...
0
votes
1answer
45 views

An Inequality Involving Prime Numbers

Let $p_i$ be the $i^{th}$ prime number. It seems as though the following inequality is true for all positive integers $m$ and real numbers $x>1$: ...
35
votes
3answers
3k views

Is $n! + 1$ often a prime?

Related to this question, I wonder how often $n!+1$ is a prime? There is a related OEIS sequence A002981, however, nothing is said if the sequence is finite or not... or anything in that sense...
0
votes
2answers
53 views

Question regardles primes and the fundamental theorem of arithmetic

I have been reading through my book of practice proofs and came across this particular question which has stumped me. $p$ and $q$ are primes. Prove $\forall p \in \mathbb{Z}, \forall k \in ...
3
votes
0answers
62 views

Resources about infinite primes of form $n^2 + 1$

Where can one find existing work on the following problem? Prove there are infinitely many primes of the form $n^2 + 1$. Resources about related work would also be appreciated.
7
votes
5answers
691 views

Induction hypothesis misunderstanding and the fundamental theorem of arithmetic.

The fundamental theorem of arithmetic is made of two parts: The existence part: There exist primes such that for any natural number $j$, we can write $j$ as a product of prime numbers. The ...
10
votes
4answers
850 views

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$

If $n = 51! +1$, Then find no of primes among $n+1,n+2,\ldots, n+50$ Really speaking, I don't have any clue ...
2
votes
0answers
58 views

Birthday problem & primes

Let $\pi_k(n)$ be the almost prime counting function, then $\pi_k(2^kn)$ reaches a max value, since $\pi_k(2^kn)=\pi_{k+1}(2^{k+1}n)$ for large enough $k$. (eg, ...
2
votes
1answer
76 views

$\text{lcm}(1,2,3,\ldots,n)\geq 2^n$ for $n\geq 7$

I can prove that $\text{lcm}(1,2,3,\ldots,n)\geq 2^{n-1}$. Newly, i read in a paper that for $n\geq 7$ we have: $$\text{lcm}(1,2,3,\ldots,n)\geq 2^n$$ Can you prove it? (this inequality is an ...
2
votes
0answers
88 views

Questions about central polygonal numbers $1, 2, 4, 7, 11, 16, 22, 29, 37, 46,\cdots$

Formula for Central polygonal numbers is $\frac{n(n+1)}{2} + 1$, if $n=1$ or $n$ is prime, we get the new sequence $A$: 2, 4, 7, 16, 29, 67, 92, 154, 191, ... It seems that all primes either is ...
3
votes
1answer
52 views

Can a Mersenne number be a power (with exponent > 1) of a prime?

Let $n \geq 1$ and consider the (Mersenne) number $M_n = 2^n-1$. Is it possible that $M_n = p^k$ for some prime $p$ and some (necessarily odd) $k > 1$? Thanks in advance.
0
votes
1answer
56 views

AP term multiple of prime number

I am having this equation : (a+(n-1)d)%p=0 Here a and d can go upto 10^18 and p is prime number upto 10^9 . How to find the least value of n here? Example : If ...
2
votes
0answers
45 views

Prime Triangle:: How to find the position(row and column) of prime number in a triangular arrangement

I was working on problem which asks the position of a prime number in a triangular arrangement. If we arrange the all prime up to 10^8 as shown in image we can find the row and column number of a ...
3
votes
1answer
66 views

Improving Bertrand's postulate

Recall that Bertrand's postulate states that for $n \ge 2$ there always exists a prime between $n$ and $2n$. Bertrand's postulate was proved by Chebyshev. Recall also that the harmonic series $$ 1 + ...
1
vote
1answer
27 views

How to combine three integers from three sequences such that all the numbers in the triplet be coprime.

So there are three sequences of integers denoted $s_1, s_2$ and $s_3$. Each of them starts at $2$ and goes up to an integer $N$. In other words, they're all identical sequences of numbers of the form ...
3
votes
4answers
116 views

Expressing $\Bbb N$ as an infinite union of disjoint infinite subsets.

The title says it. I thought of the following: we want $$\Bbb N = \dot {\bigcup_{n \geq 1} }A_n$$ We pick multiples of primes. I'll add $1$ in the first subset. For each set, we take multiples of some ...
1
vote
0answers
52 views

Wolstenholme Number

Does Wolstenholme Numbers have perfect squares other than 1 and 49? The first few are 1, 5, 49, 205, 5269, 5369, 266681, 1077749 seems to be a complicated problem
3
votes
1answer
34 views

Physical reflections of prime-number distribution

Not a purely mathematical question: I have read somewhere that Atomic Orbital is closely related to the distribution of prime numbers, but I am unable to find any reference to that. Can someone ...
1
vote
1answer
49 views

Proof for Carmichael theorem

if $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots p_r^{a_r}$ and $\lambda(n) = lcm[(p_1-1)(p_1^{a_1-1}),(p_2-1)(p_2^{a_2-1}),(p_3-1)(p_3^{a_3-1}),\dots,(p_r-1)(p_r^{a_r-1})]$ then $k^{\lambda{n}} \equiv ...
2
votes
1answer
35 views

Extrema of the Ratio of Consecutive Primes

Let $p_i$ denote the $i$th prime number. We know that $\frac{p_{n+1}}{p_n}\rightarrow 1$ as $n\rightarrow\infty$. Therefore, if we pick some real number $c>1$, there should be some positive integer ...
0
votes
1answer
59 views

The binomial coefficients $\binom{n}{ p}$ are divisible by a prime $p$ only if $n$ is a power of $p.$

I'm looking for a "high school / undergraduate" demonstration for the: All the binomial coefficients $\binom{n}{i}=\frac{n!}{i!\cdot (n-i)!}$ for all i, $0\lt i \lt n$, are divisible by a prime $p$ ...
1
vote
1answer
42 views

How many $\overline{a}\in\left(\mathbb{Z}/91\mathbb{Z}\right)^\times$ pass the Fermat and Miller-Rabin primability tests?

Let $$\text{F}_{91}:=\left\{\overline{a}\in\left(\mathbb{Z}/n\mathbb{Z}\right)^\times:91\text { passes the Fermat primality test to base }a\right\}$$ and ...
1
vote
1answer
37 views

Twin primes : prove the convergence of $ \lim_{N\sim\infty} \frac{1}{N} \sum^{N}_{p\in T} (\log(p)+\frac{1}{p})²$

let $T$ be the twin primes set : $p \in T $ if and only if $ p$ and $p+2$ are primes. Can you help me establish the convergence of : $$ \lim_{N\sim\infty} \frac{1}{N} \sum^{N}_{p\in T} ...
0
votes
0answers
40 views

Nondiagonalizable matrix with successive primes?

The 4x4-matrix filled from left to right and from top to bottom with successive primes, starting with the prime $21005627$ , is not diagonizable. Is there a 3x3-matrix with the same property ? I ...
1
vote
1answer
43 views

(p-1)! number theory problem

I was working on this little problem: Let $\frac{a}{(p-1)!} = 1 + 1/2 + 1/3 + ... + 1/(p-1)$, where p is a positive prime. (a) Prove $p\mid a$. (b) Can $p^2 \mid a$? I thought (a) was pretty ...
1
vote
1answer
82 views

Combining primes for getting primes?

I was thinking about what would happen when we combine two prime numbers $p$ and $q$ into one number $:pq:$ . Like if $p=5$ and $q=3$ , then $:pq:=53$ . Then if $p=7$ and $q= 11$ then $:pq:=711$ and ...
13
votes
4answers
571 views

Is every prime the average of two other primes?

$\forall {p_1\in\mathbb{P}, p_1>3},\ \exists {p_2\in\mathbb{P},\ p_3\in\mathbb{P}};\ (p_1 \neq p_2) \land (p_1\neq p_3) \land (p_1 = \frac{p_2+p_3}{2})$ Now I'm not a 100% sure about this, but I ...
5
votes
1answer
184 views

Why all composite numbers have this property?

Define $f(n)=\sum\limits_{A \in S} f_{1}(n,A),\ n>2,\ n \in \mathbb{Z}$, where $S$ is the power set of $\{\frac{1}{2},\cdots ,\frac{1}{n-1}\}$. Define $\ f_1(n,\varnothing)=1,\ ...
5
votes
5answers
791 views

Proof of infinitely many primes, clarification

Proof: The proof is by contradiction. Suppose there are only finitely many primes. Let the complete list be $p_1,p_2,\dots,p_n$. Let $N = p_1p_2 \dots p_n+1$. According to the Fundamental Theorem of ...