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

3
votes
0answers
80 views

The n-envelope problem

This is original problem: You have n number of envelopes, and 100 $1 bills. you have to put these bills in the envelopes in such a way that any amount between 1 to 100 can be reached just by ...
4
votes
0answers
61 views

Are large prime numbers kept secret? [duplicate]

I've read several times that modern cryptography is based on the fact that multiplying two primes is easy, whereas getting the prime factorization of a random big integer is very hard. (see here) ...
1
vote
1answer
48 views

Limit of Sum $\sum \frac{p(k+1) - p(k)}{p(k)^2}$ ? (corrected)

This is a re-post with my (corrected) earlier typo in red as a reminder. The question is about $$(A)\hspace{10mm}\lim_{n \to \infty} \sum_{k=\color{red}2}^{n} \frac{p(k +1) - p(k)}{p(k)^2} = ...
3
votes
1answer
102 views

Showing that if $p$ is prime, then $(p^4 + 4)$ can't be prime

I want to show that if $p$ is prime, then $(p^4 + 4)$ can't be prime. I guess Fermat's little theorem may help, but I can't figure out how to use it for the proof. Can anyone point me in the right ...
2
votes
1answer
93 views

Are there infinitely many prime numbers? [duplicate]

I will post my own answer below. That should not deter others from answering. There are many ways to prove this.
1
vote
1answer
26 views

Sizes of Blocks of Consecutive Integers Divisible by at Least One Prime Less than or Equal to $r$.

Let $f(r)$ be the largest integer such that there exists a block of $f(r)$ consecutive integers each divisible by some prime that is less than or equal to $r$. For example, $f(2)=1$ because it is ...
3
votes
0answers
52 views

An Inequality with Prime Numbers

Let $m\geq 8$ be an integer, and let $q$ be the smallest prime that is greater than $m$. Let $p$ be a prime that satisfies $q\leq p<q^2$, and let $p_0$ be the smallest prime such that ...
2
votes
1answer
41 views

For an integer $n \geq 2$, let $m$ be the largest positive integer less than $n$ such that $m \mid n$. [on hold]

Consider an integer $n \geq 2$, and $m$ the largest positive integer less than $n$ such that $m \mid n$. Then $n = mk$ for some positive integer $k$. Prove that $k$ is a prime number.
1
vote
2answers
216 views

Visualization of Eratosthenes’ sieve

In otherwise great paper on prime numbers, I found following visualization of Eratosthenes’ sieve: I found it somewhat scary and confusing. Is there any better visualization of Eratosthenes’ sieve ...
1
vote
0answers
42 views

Prime bounds under RH

Continuing from here, since $$ \sum_{k=1}^{\lfloor\log(n)\rfloor}\dfrac{\pi(n^{1/k})}{k}=\operatorname{li}(n)-\sum_{k=1}^{\infty}2\ ...
0
votes
1answer
36 views

Existence of at least one prime for all sequences in the family of sequences

Prove or disprove that for a fixed $n \in N$, there exists at least one prime among the integers of the form $2^{k}n+2^k-1$ for an arbitrary $k \in N$.
-2
votes
0answers
56 views

About the concept of prime numbers [closed]

I have developped a new approach of the concept of prime number and I generalized the concept to the reals ! Can you tell me what you think about it, please ? I have already published an article in a ...
0
votes
2answers
125 views

$9n^2-4$ only generates one prime? Why?

Instead of doing the work I was supposed to be doing, I played around with some numbers, and I noticed that for $n\in\mathbb{N}$, $9n^2-4$ only seems to generate a prime for $n=1$. Can anyone ...
0
votes
4answers
111 views

Is at least one of $6k + 1$ or $6k-1$ prime?

We know that any prime number ( $> 2,3$) can be written in the form $6k+1$ or $6k-1$. Is it necessary that at least one of $6k+1$ or $6k-1$ is a prime number ?
0
votes
1answer
37 views

Q: Understanding Answer of 2012 AMC 8 - #18

The problem is: "What is the smallest positive integer that is neither prime nor square and that has no prime factor less than 50?". The solution for this problem goes like this: "Since the integer ...
0
votes
0answers
53 views
+50

congruence relation between 2 primes and possible equivalent relation in polynomial ring over $GF(2)$

Let $p, q$ be primes. Then linear congruence equation, $ap \equiv r(\mod q)$ can be solved for $a$ and will have unique solution for each value of $r$ such that $a < q$. Is this right ...
1
vote
2answers
31 views

Prove that 1 is the only “common” divisor of the integers n and n+2

Let n be any odd integer. Prove that 1 is the only "common" divisor of the integers n and n+2. I think you have to find gcd(n, n+2) and say that since n odd then then n+2 will also be odd. Thus n + ...
0
votes
0answers
40 views

Fast check of safe primes or Sophie Germain primes

If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$. In ...
7
votes
1answer
162 views

Prove $18080108080 \sum_{k=0}^{1560-1} 10^{10k}+1$ is prime

I saw this fact on twitter: I would like to know how one would show this number is prime. Is there an elementary way to show that this number is prime? Is there a simplified primality testing ...
2
votes
1answer
82 views

Prime number upper bound

I am reading some written notes about a proof I do not understand, maybe some informations are missing. The result that has to be proved is the following: if $p_n$ is the $n$-th prime number, ...
1
vote
0answers
83 views

How I could transform this into product over primes :$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+…\frac{1}{2^p-1}$?

1)Can I transforme this sum into product OVER primes:$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+....\frac{1}{2^p-1}$ ? Note : p is prime number and ${2^p-1}$ is prime 2)I would be interest to know ...
0
votes
1answer
25 views

Largest $k$ such that $(p-k) = \lceil \sqrt{(p-2k) p} \rceil$

Assume $p \in \mathbb P.$ Assume $0<p-2k<p$ and the next square larger than $p(p-2k)$ is $(p-k)^2$. It is trivial to show that $p(p-2k)+k^2$ is a square. Simply $p(p-2k)+k^2 = (p-k)^2.$ ...
7
votes
2answers
256 views

Is $7^{8}+8^{9}+9^{7}+1$ a prime? (no computer usage allowed)

Prove or disprove that $$7^{8}+8^{9}+9^{7}+1$$ is a prime number, without using a computer. I tried to transform $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, unsuccessfully, no useful conclusion.
1
vote
2answers
40 views

The $i^{th}$ prime in a given ring R

When I say that $p_1=2$, I mean that the first prime in the standard ring of integers $(\mathbb{Z},*,+)$ is $2$. I was wondering whether the notion of ordering the primes like this can be generalized ...
5
votes
2answers
116 views

Is this Goldbach-type problem easy to solve?

Problem: Given an odd prime number $p$, are there odd prime numbers $q$, $p'$, $q'$ such that $\{p,q\} \neq \{ p',q'\}$ and $p+q = p'+q'$ ? This comment informs that it's an obvious ...
3
votes
2answers
96 views

Given $N$, what is the next prime $p$?

Certain data structures in programming related to collections operate in an optimal way if they have prime number of elements. This means if a program (programmer) requires $N$ (any natural number) ...
5
votes
1answer
259 views

Identity for frequency of integers with smallest prime(n) divisor

An identity for A038110 and A038111: $$ \frac{\phi(e^{\psi(p_{n}-1)})}{e^{\psi(p_{n})}}=\frac{\prod _k^{n-1} \left(1-\frac{1}{p_k}\right)}{p_n}, $$ where $\psi(\cdot)$ is the second Chebyshev function ...
4
votes
1answer
202 views

Is $2013^{2014}+2014^{2015}+2015^{2013}+1$ a prime? (usage of a computer not allowed)

Prove or disprove: $$2013^{2014}+2014^{2015}+2015^{2013}+1$$ is a prime number, without using a computer. I tried to transform the expression $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, but couldn't reach ...
2
votes
0answers
39 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 ...
29
votes
1answer
437 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
42 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
185 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
111 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
72 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
35 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
46 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
64 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
58 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
25 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
119 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
69 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
91 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
51 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
153 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
126 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
73 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 ...