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
69 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
56 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) ...
21
votes
6answers
2k views

Percentage of primes among the natural numbers

How high is the percentage of primes in $\mathbb{N}$? ($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$) The percentage has to be lower ...
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 ...
1
vote
1answer
47 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} = ...
1
vote
2answers
289 views

How many prime numbers exist all together in proportion to not prime numbers? [duplicate]

Q: If prime numbers are of infinitude, what is the proportion of not prime numbers to prime numbers? And if exist an infinitude of prime numbers, where are those not prime numbers? And what is an ...
29
votes
1answer
432 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 $$ ...
2
votes
1answer
934 views

Infinitely many primes proof correctness

I know I have already asked a question regarding this proof. However, I wanted to see if my reformulation of this proof (with my better understanding in my own words and after some time) is correct. ...
2
votes
1answer
92 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
25 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 ...
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.
5
votes
1answer
256 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 ...
3
votes
0answers
49 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 ...
0
votes
0answers
49 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 ...
7
votes
1answer
161 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 ...
0
votes
0answers
39 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 ...
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.
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$.
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\ ...
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 ...
0
votes
4answers
110 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
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 ...
-2
votes
0answers
56 views

About the concept of prime numbers [on hold]

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 ...
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
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 ...
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 + ...
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 ...
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
1answer
126 views

Why isn't $1$ a superior highly composite number?

A superior highly composite number is a positive integer $n$ for which there is an $\epsilon>0$ such that $\dfrac{d(n)}{n^\epsilon} \geq \dfrac{d(k)}{k^\epsilon}$ for all $k>1$, where the ...
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 ...
5
votes
12answers
913 views

What are the properties of a prime number?

For instance, we know that odd numbers behave like: $$x = 2y + 1 \quad\text{where}\quad x,y\in\mathbb Z$$ For even numbers: $$a = 2b \quad\text{where}\quad a,b\in\mathbb Z$$ But what about prime ...
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^+}, ...
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.$ ...
3
votes
1answer
78 views

Prime number question

Can somebody please give me a hint on how to start this question: Let $a$ and $n$ be two positive integers with $a,n ≥ 2$. Assume that $a^n−1$ is a prime number. Prove that $a = 2$ and $n$ is a prime ...
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) ...
3
votes
1answer
128 views

What is the 5000th happy prime number?

Im writing a program that finds the Nth happy prime number. I think it works, but to double check I want to compare what it returns for the 5000th happy prime number. The problem is, I dont know where ...
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 ...
2
votes
2answers
556 views

Bijection between Prime numbers and Natural numbers

We know that if set $S$ is countable then this set and set of all natural numbers are equivalent, which means that there must be some bijection between this two sets $F:S\rightarrow N$. We know that ...
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
38 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
43 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 ...
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? ...
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 ...
1
vote
1answer
67 views

Sum of reciprocals of primes for known primes.

I was reading through some old analytic number theory notes earlier and found the interesting fact that even though $\sum\frac{1}{p}$ diverges: $\sum_{\text{known primes}}\frac{1}{p} < 4$. ...
10
votes
4answers
1k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
1
vote
2answers
68 views

Power of primes

We have proved that if $a > 3$, then $a$, $a+ 2$, and $a+ 4$ cannot be all primes in previous question. Can we say that they all be powers of primes?
3
votes
2answers
85 views

Extending primes

This question is more of a curiosity than anything. Start with a prime number and consider concatenating digits onto the right hand side. Sometimes you can make a prime and continue the process ...
1
vote
2answers
117 views

Prime factorization, distinct primes

Let $n=p^eq^f$ where $p$ and $q$ are distinct primes and $e$ and $f$ are positive integers. Show that $n$ has $(e + 1)(f + 1)$ distinct factors in $N$, and that the sum of all these factors is ...
1
vote
1answer
288 views

Sum of three primes equal to a prime [closed]

Does anyone know how to always get a prime from the sum of three primes? For example: 5+7+11=23, 17+29+43=89, etc.