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

0
votes
1answer
59 views

Let p be an odd prime number. Then show the following:

Let $p$ be prime, $p \geq 3$. Then show that $K_p$ is the union of $\frac{1}{2}(p-1)C_p$. I am once again at a loss for a starting point. Maybe just a small hint so I can work through this myself ...
2
votes
2answers
779 views

question about prime numbers [on hold]

Prove that for all odd prime numbers $p_1$ and $p_2$, there exist prime numbers(exclude 2) $p_3$ and $p_4$ such that $$p_3 + p_4 = p_1 + p_2 + 2.$$ Hints would be appreciated.
1
vote
0answers
35 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 ...
1
vote
2answers
64 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 ...
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
15 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 ...
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 ...
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 ...
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{ ...
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
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 ...
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 ...
28
votes
3answers
18k views

Why are very large prime numbers important in cryptography?

Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others. Secondly, a friend asked me recently why large primes are important for data security, and I was ...
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 ...
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 ...
58
votes
5answers
7k views
1
vote
2answers
118 views

Show that if $p$ is an odd prime, show a power $p^k$ can never be a perfect number

Show that if $p$ is an odd prime, show a power $p^k$ can never be a perfect number. I am little confused about this problem, any insight?
5
votes
1answer
854 views

Super Perfect numbers

A super-perfect number is a number with $\sigma(\sigma (n))=2n$. How can I prove that every even super perfect number is from the form $n=2^k$ when $2^{k+1}-1$ is prime. I tried every way please ...
4
votes
2answers
649 views

Can powers of primes be perfect numbers?

I need to prove the following, though I'm not 100% certain I understand the definition of a perfect number. Prove that no perfect number is a power of a prime. First of all, I'm assuming that ...
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 ...
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
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!$
2
votes
3answers
142 views

Explain the proof that the root of a prime number is an irrational number

Though the proof of this is done in a previous question, I have some doubt about a certain concept. So I ask to clarify it. In the proof we say that $\sqrt{p} = \frac{a}{b}$ (In their lowest ...
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 ...
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 ...
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\ \ ...
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: ...
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
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
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 ...
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
3answers
65 views

At what rate are composites removed in a set after each prime multiple is cancelled out?

I was looking at sieves today, mainly sieving for primes and I noticed a pattern type thing. As I crossed out primes in a small set, the number of composites that were crossed out decreased. I haven't ...
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 ...
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
votes
2answers
56 views

Proof for whether or not a function will ever be non-prime.

From the proof that there are infinitely many primes: Given all the primes $p_i$ known up to the $n$th prime, construct the number $q_n$ such that $$ q_n = 1 + \prod^{n}_{i=1} p_i $$ Since there is ...
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 ...
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 ...
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 ...
14
votes
1answer
160 views

Simple(r) proof that $\pi(2^n)\geq n$?

We can clearly prove that $\pi(2^n)\geq n$ with Bertrand's postulate, but that seems like overkill. Is there any simpler way one can prove that $\pi(2^n)\geq n$? Note: $\pi(m)$ is the prime ...
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 ...
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 ...