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
34 views

Can you estimate the difference of primes between numerator and denominator?

Let $p_n$ the nth twin prime, it is $p_n$ is a prime number and $2+p_n$ is also a prime. It is well know that Brun's theorem states (unconditionally) that $$\mathcal{B}=\sum_{n\geq ...
0
votes
2answers
22 views

A question about Prime Numbers (and its relation to RSA Asymmetric Cryptography)

Can someone kindly help me with the following question. Please bare in mind I am not good at maths, but I do get concepts, so I am looking to see if my current conceptual understanding is correct ...
2
votes
1answer
14 views

How to work out the greatest lower divisor in a pair of divisors?

I don't know what it's called, so it's hard to explain, but say we have the number $12$, which can be $1 \times 12$, $2 \times 6$, or $3 \times 4$. I want the $[3, 4]$ pair because $3$ is the ...
1
vote
2answers
63 views

Find all primes $p,q$ and even $n > 2$ such that $p^n+p^{n-1}+\cdots+1 = q^2+q+1$

Find all primes $p,q$ and even $n > 2$ such that $p^n+p^{n-1}+\cdots+1 = q^2+q+1$. Attempt The first thing I would do is simplify the geometric series to $\dfrac{p^{n+1}-1}{p-1} = q^2+q+1$. I ...
3
votes
2answers
77 views

Can you get a closed-form for $\prod_{p\text{ prime}}\left(\frac{p+1}{p-1}\right)^{\frac{1}{p}}$?

When I use the Taylor expansion series for $$\log(1+x)^{1+x}+\log(1-x)^{1-x}$$ with $x=\frac{1}{p}$, $p$ prime, I believe that I can deduce $$\sum_{p\text{ ...
0
votes
0answers
36 views

Probability that a given function is prime…

If we have a set of primes $p_1$, $p_2$, ... , $p_n$, we can easily construct a function of their product: $$f(\alpha) = \alpha \left( \prod_{k=1}^n{p_k} \right) + 1, \alpha \in \mathbb{N}$$ I'm ...
4
votes
1answer
26 views

What about $\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n$ when $y=[x]\to\infty$?

For a real $x\geq 2$ and when we take $y= [x]$ its integer part, I am trying to study the asymptotic size or growth of $$\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n,$$ I believe that ...
0
votes
0answers
44 views

$2^k+3$ : Primality Brute Forcing Theory Below The Square Root

I'm testing a theory of brute forcing $2^k+3$. I've tried to test $(2^k)+3$ where $k=84$ but my computer just takes too long... Java takes too long too.. It's pretty stupid to assume 83 tests makes ...
18
votes
4answers
3k views

Prove that 10101…10101 is NOT a prime.

So basically we have a number $10101...10101$ that contains $2016$ zeros and can be written as$ \sum _{ k=0 }^{ 2016 }{ 100^{ k } }$ . I want to prove that this number is not a prime without using ...
2
votes
0answers
23 views

Is always two times an even semiprime at a distance $1$ or prime to the closest previous odd semiprime?

This is an observation regarding the semiprimes, also named 2-almost primes, biprimes, or the product of two primes. This week I do not have a computer, only a tablet (hospitalized with a lot of free ...
2
votes
0answers
29 views

Is there a short proof of the existence of $a$ so that $a$ is a primitive root for infinitely many primes $p$?

After looking for a general answer I found Artins conjecture, and I was happy to see so much is known. However I don't know nearly enough to follow the proof, yet it bothers me I can't prove the ...
0
votes
0answers
54 views

Hypothetical proof of Goldbach's conjecture? [on hold]

Goldbach's conjecture: Every even number greater than 4 is the sum of two prime numbers. An equivalent statement is; For all $n\geq 2$ there exists a number $e(n)$ such that $n-e(n)$ and ...
0
votes
0answers
27 views

Is there a proof that $(n-2x)! \times n^{2x-1} > n!$ (where $x$ is a function related to the prime counting function

Is it possible to prove the following? Let $\pi$ be the prime counting function and $A(n)=\pi(2n)-\pi(n)$ $(n-2A(n))! \times n^{2A(n)-1} > n!$
4
votes
2answers
69 views

Prime counting function; when is it true that $\pi(n) > \pi(2n) -\pi(n)$?

Let $\pi$ be the prime counting function. Under what conditions is it proven true that $\pi(n) > \pi(2n) -\pi(n)$, if at all?
0
votes
2answers
41 views

How to check if a a relatively small number is prime (4 digits at most)?

I have an undergrad degree. Either I missed it or they didn't teach us, but how can I check (without using a computer) if a number, say 1033, is prime?
0
votes
0answers
15 views

Show that $s(x)=\pi(x)/x+\int_1^x \frac{\pi(t)}{t^2}\,dt$

For $x\in\mathbb{R}$, let $\pi(x)=\#\{$ primes $p:p\le x\}$ and let $s(x)=\sum\limits_{\text{primes}} \frac{1}{p}$. Given that: If $a_1, a_2, \dots \in \mathbb{R}$ and $f$ is a $C^1$ function in an ...
2
votes
2answers
38 views

Generalizing Legendre's Theorem on prime factorization of factorials

From Legendre's Theorem we know $$n!=\prod_{p}p^{\lceil \frac{n}{p}\rceil +\lceil \frac{n}{p^{2}}\rceil +.. }$$. Since $\Gamma (n+1)=n!$, i wonder if there is a generalization of this formula for ...
2
votes
2answers
34 views

Is there an alternative approach to the definition of prime numbers based on the definition of the natural logarithm?

Is there an alternative approach to the definition of prime numbers based on the definition of the natural logarithm? These are my thoughts about it, the questions are at the end: Basically when a ...
1
vote
1answer
48 views

How I can prove that for any natural number $n$ such that $30<n$, $\pi(4n-3)<n$?

I need to proove that for any natural number $n>30$: $$\pi(4n-3)<n.$$ In this inequality, $\pi(x):\mathbb{N}\to \mathbb{N}$ is the defined as follows: $$\pi(x):=Card(\lbrace p \ | \ p\leq x\ \ ...
1
vote
1answer
47 views

Find all $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime

I'll try to format my question in a manner such that you can skip (irrelevant) parts. Exercise: Find all natural $n$ such that $3^{2n+1}-4^{n+1}+6^n$ is prime. Motivation: I'm trying to ...
3
votes
2answers
79 views

Product of Primes

Let $\mathbb{P}$ denote the set of prime numbers. How would one evaluate $$\prod_{p\in \mathbb{P}}\frac{p-1}{p}$$ I do not think that the fact that ...
3
votes
3answers
77 views

For what numbers $n$ is $\sqrt{n}$ irrational?

I would say it has something to do with the numbers that can be expressed as a factor of different prime numbers, but when I get to $8$, that can be changed to $2^3$, which goes against this. Is there ...
11
votes
2answers
102 views

How was the 506-digit prime number 999…9998999…999 found?

I was surprised to encounter a claim made on the internet that the following number is prime: ...
39
votes
8answers
2k views

$-1$ as the only negative prime.

I was recently thinking about prime numbers, and at the time I didn't know that they had to be greater than $1$. This got me thinking about negative prime numbers though, and I soon realized that, for ...
0
votes
0answers
31 views

Is there an arbitrarily large set of naturals so that the sum of each two has exactly $n$ prime divisors? What about an infinite set? [closed]

Is there an arbitrarily large set of naturals so that the sum of each $2$ has exactly $n$ prime divisors where $n$ is fixed? What about an infinite set? For $n=1$ this is clearly false, what ...
1
vote
2answers
66 views

How can Mersenne Prime rule be valid if $2047$ isn't prime?

The rule of Mersenne Prime says that $2^p - 1$ is prime if $p$ is prime. $2^{11} - 1 = 2047$ satisfies the condition, but it's not a prime as it can be divided by two prime numbers $23$ and $89$. ...
0
votes
2answers
26 views

Euler's proof of Infinitude of Primes: If a prime divides an integer, why would it have to divide 1?

Here's the Euler's proof of Infinitude of Primes in Rosen's Discrete Mathematics: We will prove this theorem using a proof by contradiction. We assume that there are only finitely many primes, ...
0
votes
0answers
23 views

Prime division algebra level 5

Let $P$ be the number of integers $n$  for which $n^4-52n^2+595$ is prime, and let $D$ be the number of distinct primes that can be represented in this form. Find $P+D$.
2
votes
0answers
19 views

Finite amount of consecutive smooth numbers

is there a short proof of the fact that there is a finite amount of consecutive smooth numbers (meaning Given a finite set B, there is a finite amount of pairs $n,n+1$ so that both can be expressed as ...
0
votes
0answers
19 views

What are some easy to prove results on the density of primes?

Bertrand's postulate states that for any integer $n>3$, there's always a prime $p$ between $n$ and $2n-2$. That result sets a reasonable 'lower bound' on how often we can expect primes to show up, ...
1
vote
1answer
31 views

How does the fact that Fermat primes are relatively prime imply there are infinite primes?

I was just reading a book called Proofs from the Book. It presented the proof given by George Polya to prove that two Fermat primes (numbers of the form $2^{2^n} + 1$) are always relatively prime, ...
1
vote
2answers
39 views

Prove that there exists infinitely many primes of Digital root $2,5$ or $8$

I am highly interested in properties of digital root. Digital Root: Digital root of a number is a digit obtained by adding digits of number till a single digit is obtained. It's clear that Digital ...
3
votes
3answers
73 views

How can I prove that only there continuous odd prime are $3,5,7$?

How can I prove that the only prime number $p$, such that $ p,p+2,p+4$ are primes is 3?
1
vote
0answers
16 views

Does there exist a $k$ such that for all $n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$?

Does there exist a $k \in \mathbb{R}$ such that for all $n \in \mathbb{N}, n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$, where $\text{gpf}(x)$ is the greatest prime factor of $x$? I ...
1
vote
0answers
65 views

A method of writing all primes

I've recently noticed a method of describing primes. As an example: $13=5*11-2*3*7$. This pattern must follow these rules: $x-y$ such that $x*y$ is the product of all previous primes (allowing powers ...
11
votes
1answer
92 views

Is there a polynomial such that $F(p)$ is always divisible by a prime greater than $p$?

Is there an integer-valued polynomial $F$ such that for all prime $p$, $F(p)$ is divisible by a prime greater than $p$? For example, $n^2+1$ doesn't work, since $7^2+1 = 2 \cdot 5^2$. I can see that ...
2
votes
1answer
29 views

Complexity of generating a prime larger than $N$

Is it provably difficult to generate a prime larger than a prescribed $N$? For instance, if I want a prime of $1000$ digits, is there a way to do that deterministically, i.e., without resorting to AKS ...
11
votes
0answers
73 views

Consecutive prime numerators of harmonic numbers?

Let $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\frac{a}{b}$$ and let $a$ and $b$ are coprime, $h_{n}=a$. $h_{n}$ is prime for ...
0
votes
0answers
31 views

Find k-th element of the sequence

Please, help me with effective algorithm to: Find k-th element of the sequence {n | (6n-1), (6n+1), (12n+5) are primes} Find k-th element of the sequence {n | (6n-1), (6n+5), (12n-7) are primes}
2
votes
1answer
30 views

Sum of reciprocals of n-digit primes

I have observed, by calculation, that the sum of the reciprocals of all the n-digit prime numbers is approximately 1/n, and that this becomes increasingly accurate as n increases. Is there a simple ...
7
votes
2answers
130 views

Is $k+p$ prime infinitely many times?

I have the following conjecture: Let $k\in\mathbb{N}$ be even. Now $k+p$ is prime for infinitely many primes $p$. I couldn't find anything on this topic, but I'm sure this has been thought of ...
0
votes
1answer
42 views

What is the simplest way to show that ${(p-1)! \over (k)!(p-k)!}$ is an integer?

In the proof of $p$ | $\binom{p}{k}$ (p divides $\binom{p}{k}$) where $p$ is prime, what is the simplest way to show that $${(p-1)! \over (k)!(p-k)!}$$ is an integer?
0
votes
1answer
19 views

The form of solutions of $p*k-q*j=r,$ for $(p,q)=1$.

I would like to find the form of solutions of $p*k-q*j=r,$ for $(p,q)=1$ for any fixed $r < pq$ and $k,j \in \mathbb{N}$. I tried to look at the divisibility of $p=cq+b.$ But I didn't have any ...
4
votes
1answer
43 views

Aren't Legendre's conjecture and Andrica's conjecture same?

If Legendre's conjecture is true, couldn't we easily obtain $\sqrt{p_{n+1}}-\sqrt{p_{n}}<1$ where $p_{n}$ is the $n$th prime? $$p_{n+1}<(\lfloor \sqrt{p_{n}} \rfloor + 1)^{2}<( \sqrt{p_{n}}+ ...
0
votes
1answer
40 views

Proving the primality of these large numbers?

In 2007, Vautier claimed that the largest known consecutive pair of prime numbers (at the time) was $2003663613\cdot2^{195000}-1$ and $2003663613\cdot2^{195000}+1$. I was wondering how Vautier found ...
1
vote
2answers
85 views

Using binomial theorem to prove $a | b^n \Rightarrow a | b$. ( | is divides, a prime, n integer > 1)

I tried expanding $(b-a+a)^n=$[$(b-a)+a$]$^n$ but it just seemed to further complicate the problem. I also tried to prove the contrapositive but that doesn't seem to lead to anywhere to. Is there any ...
2
votes
1answer
74 views

How does one prove that $2\uparrow\uparrow16+1$ is composite?

Just to be clear, close observation will show that this is not the Fermat numbers. I was reading some things (link) when I came across the footnote on page 21, which states the following: ...
10
votes
3answers
387 views

BMO2 2016 Number Theory Problem

Suppose that $p$ is a prime number and that there are different positive integers $u$ and $v$ such that $p^2$ is the mean of $u^2$ and $v^2$. Prove that $2p−u−v$ is a square or twice a square. Can ...
1
vote
1answer
39 views

estimation for n-th prime

The famous theorem of Hadamard and Vallee-Poussin https://en.wikipedia.org/wiki/Prime_number_theorem implies that $p_n\sim n\ln n$, so $C_1 n\ln n \le p_n \le C_2 n\ln n$ holds for all $n\ge 2$ with ...
0
votes
2answers
37 views

On analogy between $\Bbb Z$ and $\Bbb F_q[x]$

There are objects and operations analogous between $\Bbb Z$ and $\Bbb F_q[x]$. For example primes in $\Bbb Z$ and irreducibles in $\Bbb F_q[x]$ are analogous and so is multiplication operation. ...