Prime numbers are natural numbers greater than 1 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
90 views

Legendre's Conjecture: Bounded Prime Gaps

I have encountered some error in the details of what Legendre's conjecture implies about bounded prime gaps. So I am working to correct errors and to state both what is conjectured and what is implied ...
5
votes
1answer
73 views

A positive integer $n$ is prime iff $\varphi(n)! \equiv -1 \pmod n$

Is this proof acceptable ? Theorem 1 (Wilson) A positive integer $n$ is prime iff $(n-1)! \equiv -1 \pmod n$ Theorem 2 A positive integer $n$ is prime iff $\varphi(n)! \equiv -1 \pmod n$ . ...
-1
votes
1answer
118 views

Gaps between primes: bounds - a question of possibilty

Let $n$ be any given natural number. Let $p$ be the very next prime greater than $n$. Let $b$ be the bound for the prime gap above $n$. Here, the bound is strictly the limit from $n$ to $p$, meaning ...
0
votes
1answer
25 views

Bounded by a constant?

What exactly is meant by "constant" when it is said that Legendre's conjecture implies that the upper bound on the prime gap above n could be bounded by the product of a constant and the square root ...
1
vote
1answer
57 views

A question about amicable numbers

http://en.wikipedia.org/wiki/Amicable_numbers I'm doing a research on amicable numbers and I wanted to write $p$, $q$ and $r$ numbers of Thābit ibn Qurra theorem. I tried to write $p$ and $r$ in ...
2
votes
1answer
129 views

Primes of the form $x^2+ny^2$

The problem of the characterization of primes of the form $p=x^2+ny^2$ is solved (e.g. in the book of Cox), and there are also a few examples for special numbers $n$. My question is: Does anyone ...
16
votes
3answers
557 views

Solving $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$

Find all positive integers $k$, positive integers $e_i$, and distinct prime numbers $p_i$ for $1\le i\le k$, such that $$p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}.$$ Is this ...
3
votes
2answers
244 views

Find all primes of the form $2^{2^n} + 5$ for a nonnegative integer n

I'm a little lost on how to do this problem. It looks a lot like the definition for the Fermat numbers: $F_n = 2^{2^n} + 1$, however I'm not sure how to use that in order to find all of the primes of ...
5
votes
0answers
223 views

Does this prime generating way generate all the prime numbers?

I've thought of the following algorithm to find the entire list of prime numbers: Take a prime number $p$ to your list. $1.$ Multiply all the numbers in your list and call the number you get ...
1
vote
0answers
42 views

Questions about primes made from consecutive numbers starting from 1

Similar to: Does there exist a prime that is only consecutive digits starting from 1? Let $b_n=\overline{a_1a_2a_3\dots a_n}$ and $a_n=n$. For example $b_{11}= 1234567891011$. I have a couple of ...
0
votes
2answers
236 views

A New, Possible Proof of the Infinitude of the Primes?

$$1=1$$ $$2=2$$ $$3=3$$ $4=2\cdot2$ At $4$, the first prime number, $2$, is there as a factor. So I say that at the square of $2$, $2$ comes into play as a prime factor. At this point, $2$ is the ...
5
votes
3answers
226 views

Are there infinitely many primes of the form $n!+1$?

For some numbers $n!+1$ is prime, but all such numbers are not prime. For example, $5!+1 = 11\times 11$. The question is this: Are there infinitely many primes of the form $n!+1$?
2
votes
1answer
32 views

If I want to learn to count in another base to calculate primality, which one should I try?

I've heard base 12 is better, but what about base 30 ? Learning multiplication tables in another base would be quite fastidious, so I don't know if that already been tried before... (I don't know ...
1
vote
1answer
34 views

distribution of elements related to prime numbers

here is my question. Fix any prime $p$ and consider the set of all elements of the form $\frac q{p^k}$, where $q$ is any other prime and $k$ is the unique integer such that $\frac q{p^k}$ belongs to ...
1
vote
1answer
69 views

A question concerning a lower bound of $\pi (n)$

In the number theory course, I was asked to prove the following: $$2^{\pi(n)} \sqrt{n} > n \mathrm{\, for\, all\, } n > 1 \in \mathbb{N}$$, where $\pi(n)$ denotes the number of prime number ...
1
vote
2answers
87 views

proportion of primes in a polynomial sequence

It is conjectured (Bunyakovsky) that when $P(x)$ is a polynomial from $\mathbb{Z}[X]$, irreducible, with positive leading coefficient and so that the integers $P(n)$ , $n\gt0$ do not share a common ...
0
votes
2answers
137 views

Why does not the perfect number formula imply there are infinitely many perfect numbers?

We know the even perfect number formula is $2^{p-1}(2^p − 1)$ and it is known that the multiplication of a even number and odd number is a even number. So why can't we say there are infinitely many ...
1
vote
1answer
51 views

No. of solutions of two equations?

What is the number of distinct primes $p$ such that $$\binom{\frac{p+1}2}2\ =\ 5\cdot r\cdot q$$ where $5<r<q<p$ are primes. (See the answer given by avz2611 in the following). Similarly, if ...
4
votes
2answers
159 views

Is this statement equivalent to Legendre's conjecture?

The maximum distance from any given number n to the next prime is less than twice the square root of n. Is this statement equivalent to Legendre's conjecture? Is this statement worded correctly? If ...
1
vote
3answers
73 views

The Largest Prime Less Than the Square of a Prime

The first prime is two. Two squared is four. The largest prime that is less than four is three. The set of primes is 2,3,5,7,11,13,17,19,23,29,31... The set of their squares is ...
0
votes
1answer
127 views

Does Bertrand's Postulate give us the tightest proven upper bound for prime gaps?

Bertrand's Postulate asserts that there is a prime between $n$ and $2n$. Is this the best such upper bound on prime gaps known today, or have stronger estimates been proved? I mean results of the ...
2
votes
4answers
44 views

Prime numbers and divisibles

I was wondering that in the process of checking if a number is a prime number, would it be reasonable to suggest that if it cannot be divided by 2, 3, 5, 7 or 9 then it could be considered a prime ...
0
votes
2answers
111 views

Any technique to manually find the prime decomposition of a number less than 3000?

I've seen a question in a math exam, asking to find the prime decomposition of 2014. It's 2*19*53. I found it odd and a little fastidious at first to try to find the multiples of 1007, trying to ...
2
votes
1answer
88 views

Proof concerning specific class of Proth numbers

Is this proof acceptable ? Theorem Let $N = k\cdot 2^n+1$ with $n>1$ , $k<2^n$ , $k$ odd and $3 \nmid k $ , thus $N$ is prime iff $3^{\frac{N-1}{2}} \equiv -1 \pmod N$ Proof Necessity ...
5
votes
5answers
2k views

Prime number between $n$ and $n!+1$

I am trying to prove that ($\forall \ n\in\mathbb{N}$) there exists a prime number $q$ such that $n < q \le 1 + n!$ I have made a graph with $n=0$ through $n=10$ and found solutions to all of them ...
0
votes
1answer
189 views

Upper bound for the prime gap above $n$

Imagine each natural number as a point in space along a path on which one can stand and walk. Imagine standing at any one point and looking forward toward the next prime. If we stand at $1$ and look ...
4
votes
1answer
91 views

If $n-1$ is $f(n)$-smooth, $n$ is prime infinitely often. What is the best $f$?

If $n-1$ is $f(n)$-smooth, $n$ is prime infinitely often. What is the best $f$? For all primes $p$, $p-1$ is $\frac{p}{2}$-smooth, so $f(n) = \frac{n}{2}$ works. If $q$ is a Fermat prime, then ...
3
votes
0answers
103 views

A question on the Prime number theorem

Let $N\geq1$. Could we infer $$\sum_{n\leq N}\mu(n)\ll N\exp(-c\sqrt{\log N})$$from $$\sum_{n\leq N}\Lambda(n)= N+O(N\exp( -c\sqrt{\log N})$$or $$\sum_{p \leq N}1=Li(x)$$ without resorting to the ...
11
votes
2answers
322 views

Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
3
votes
1answer
139 views

Does there exist a finite set of polynomials which do not have roots over any prime field?

The polynomial $x^2 + 1$ has a root in $Z_p$ if and only if $p \not\equiv 3 \mod 4$, and the polynomial $x^2 + x + 1$ has a root in $Z_p$ if and only if $p \not\equiv 2 \mod 3$. So each of the ...
0
votes
1answer
67 views

Can two different sets of prime numbers sum up to the same value

Assume A is a set of prime numbers with no duplicate elements B is a set of prime numbers with no duplicate elements A is not equal to B Cardinality of A is equal to cardinality of B Is it ...
2
votes
2answers
77 views

For which primes $p$, $p+10$ and $p+14$ are also primes?

For which primes $p$, $p+10$ and $p+14$ are also primes? I assume it has something in common with division (whether the prime $n$ is divisible by some number), but that is just the first idea that ...
1
vote
1answer
96 views

Let x >= 2. Show that if x is not divisible by any positive integer n satisfying 2<= n<=sqrt(x) then x is a prime number.

A proof is required, but I'm not sure how to do it. Could anyone guide me?
2
votes
5answers
2k views

Is it true that $n^2+3n+13$ is prime for all $n\in\mathbb ℤ^+$?

Prove or disprove the statement: If $n\in\mathbb ℤ^+$, then $n^2+3n+13$ is prime. I am lost here. All I know is that $n$ is greater than or equal to one, since it is a positive integer.
65
votes
8answers
7k views

The myth of no prime formula?

Terence Tao claims: For instance, we have an exact formula for the $n^\text{th}$ square number – it is $n^2$ – but we do not have a (useful) exact formula for the $n^\text{th}$ ...
2
votes
3answers
261 views

Square in Interval of Primes

Denote by $a_n$ the sum of the first $n$ primes. Prove that there is a perfect square between $a_n$ and $a_{n+1}$, inclusive, for all $n$. The first few sums of primes are $2$, $5$, $10$, $17$, $28$, ...
0
votes
1answer
59 views

Proving an inequality on the sum of $\log$ of primes.

Let $S(x)=\sum_{p\leq x} \ln(p)$ where $\sum_{p\leq x}$ denotes a summation over the positive prime numbers that are $\leq x$ Prove that $\forall n \in \mathbb N, S(2n+1)-S(n+1)\leq ...
1
vote
2answers
43 views

Show inequality for the number of different prime factors

We consider the function $k(n) $ that represents the number of the different prime factors of $n$.We want to show that for $n>2$ $$k(n) \leq \frac{\log n}{\log \log n}(1+O((\log \log n)^{-1})) ...
0
votes
1answer
100 views

Half prime numbers?

I am wondering if there is a term for a number which is only divisible by its square root, one and itself? For examle $25$ can be divided by $1, 5$ and $25$. And $169$ with $1, 13$ and $169$. I am ...
2
votes
1answer
190 views

New mathematical constant formed by continued fraction with prime numbers?

Notational convention: $$\bigoplus_{k=0}^{\infty}a_k=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\ddots}}}}$$ Let $$ P:=\bigoplus_{k=1}^{\infty}p_k$$ where $p_k$ is the k-th prime ...
1
vote
2answers
697 views

Upper bound number of distinct prime factors

I want to prove that if $\omega (n)$ is the number of distinct prime factors of $n$ for $n>2$ we have $\omega (n) \leq \frac{\ln n}{\ln \ln n} + O(\frac{\ln n}{(\ln \ln n)^2})$. How can I do this? ...
1
vote
1answer
207 views

Prime factorization of 2^(16) - 1

Trying to show the the prime factorization of $$2^{16}-1$$ without a calculator. I know that $2^{16} - 1$ yields the prime numbers$$3*5*17*257$$ because I calculated $2^{16}-1$ on my calculator ...
0
votes
4answers
41 views

Let $p \geq 5$ and prime. Show $p^2 + 2$ is divisible by three.

I know I have to use the division algorithm to put into the form $p^2 + 2 = 3q + r$ but everything I've tried after that has lead me to a dead end. I've mainly been trying to show $r=0$ or to make the ...
0
votes
1answer
136 views

Prime number theorem lemma: prove that $\psi(x)\sim\pi(x)\log(x)$

I'm trying to follow the proof in Wikipedia that the PNT is equivalent to the assertion $\psi(x)\sim x$, by proving that $\psi(x)\sim\pi(x)\log x$, which it claims is a very simple proof. One ...
0
votes
6answers
84 views

If $p > 5$ is a prime number, then the last digit of $p^4-1$ is $0$.

If $p > 5$ is a prime number, then the last digit of $p^4-1$ is $0$ (ex.: $7^4-1=2400$). How do I prove this?
2
votes
6answers
461 views

Proof that every number has at least one prime factor

Prove that for $ n \geq 2$, n has at least one prime factor. I'm trying to use induction. For n = 2, 2 = 1 x 2. For n > 2, n = n x 1, where 1 is a prime factor. Is this sufficient to prove the ...
2
votes
1answer
196 views

Bijection between Natural numbers and Infinite Cartesian product of Natural numbers?

Consider a function $f(n): \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N} \times ...$ mapping each number $n$ to the set of exponents to raise each prime number $p$ to in order to obtain $n$. For ...
0
votes
1answer
49 views

Length in time to find the longest range of primes between 2 and a 13 million character digit?

I am trying to run a program that tells me how many prime numbers there are in a range of numbers. I run it in intervals of 10,000 to 100,000. How long would the program take to determine all the ...
1
vote
0answers
61 views

Prime numbers that fits in a specific pattern

Any series $\displaystyle \sum_{k=0}^{\infty}a_k2^{-k}$, where $a_k\in\{0,1\}$, converges to some $x\in[0,2]$ and since the sequence $a_n$ is unique for each $x\in[0,2]$ there is an bijection between ...
0
votes
1answer
59 views

As$\ n \to \infty$, how does a product over the primes less than$\ p_n$ equal the same product over the primes less than$\ n$? [duplicate]

How is$$\ \lim_{x\to \infty} \log \log x \prod_{i< \log x} \frac{p_i -1}{p_i}= \\ \lim_{x\to \infty} \log \log x \prod_{p < \log x}_{p prime} \frac{p-1}{p}$$?