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

Gaps between primes: bounds

Legendre's conjecture implies that the prime gap above any natural number $n$ is bounded by the product of a constant and the $\sqrt n$. Actually, I have strong reason to think that this factor by ...
0
votes
1answer
6 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
26 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 ...
0
votes
1answer
68 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 ...
3
votes
0answers
56 views

Calling all genius: $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 integer $e_i$ and prime number $p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}$ for $k\ge 1$. Is this impossible or what? I've been trying for at least a week. I've ...
-1
votes
0answers
36 views

show that n is prime if and only if $S(n)0$ [on hold]

show that n is prime if and only if $S(n)0$ $S(n)={[\pi.\dfrac{(n-1)!+1}{n}]}$
5
votes
0answers
110 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
29 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
143 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 ...
3
votes
3answers
78 views

Are there infinitly 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
24 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 ...
0
votes
1answer
28 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 ...
-2
votes
0answers
61 views

Where Are the Primes In Relation To the Perfect Squares? How Are the Perfect Squares Arranged Along the Natural Number Line? [on hold]

The question is concerning the location of any given prime which satisfies Legendre's conjecture, or simply, any given prime. Do they not all? All primes > 3 are in the pair of arithmetic progressions ...
1
vote
1answer
48 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
56 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
52 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
41 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
113 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
49 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 ...
2
votes
4answers
34 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
1answer
31 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 ...
1
vote
0answers
32 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 ...
4
votes
4answers
1k views

Prime number between n and (1+n!)

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 ...
-2
votes
2answers
26 views

Prove that for a prime number $p$ and an arbitrary natural number n$\ge$ 1 it holds that gcd(p,n) is either equal to 1 or to p. [closed]

Prove that for a prime number $p$ and an arbitrary natural number n$\ge$ 1 it holds that gcd$(p,n)$ is either equal to 1 or to $p$. i just dont know where to start with this proof, it is a homework ...
0
votes
1answer
83 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 ...
3
votes
1answer
52 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
76 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 ...
8
votes
1answer
208 views
+500

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
68 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
27 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 ...
1
vote
2answers
44 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
21 views
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.
45
votes
6answers
5k 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}$ ...
1
vote
3answers
103 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
27 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
20 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
34 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
150 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 ...
0
votes
0answers
38 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? ...
0
votes
0answers
54 views

Relation between Galois theory and Fermat primes

I am curious about a possible relation between Galois theory and Fermat primes. There is a general solution to any polynomial equation of degree less than or equal to $4$. The only Fermat primes (of ...
0
votes
1answer
48 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
29 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
49 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
0answers
42 views

Mapping set of integers to irrational numbers.

Mapping Integers to Irrationals..maybe even primes? Hi i'm an undergrad currently working on a research project. I recently thought of a question that I believe would help me greatly,but have ...
0
votes
6answers
70 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?
0
votes
6answers
68 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
34 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
39 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
40 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 ...