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

3
votes
2answers
116 views

Can anyone sketch the proof or provide a link that there is always a prime between $n^3$ and $(n+1)^3$

In a recent forum discussion on number theory, it was mentioned that A. E. Ingham had proven that there is always a prime between $n^3$ and $(n+1)^3$. Does anyone know if there is a link available on ...
2
votes
1answer
96 views

Solutions to $y^2 = x^3 + k$?

As you know, the equation $y^2 = x^3 + k$ for $k = (4n-1)^3 - 4m^2$, with $m, n \in \mathbb{N}$ and no prime number that p is congruent to 1 modulo 4 count m, don't have any answer and its proof can ...
12
votes
1answer
116 views

Are there infinitely many pairs of primes where one divides one more than the square of the other?

I have the following question on number theory that is eating my head. Are there infinitely many primes $p,q$ such that $p | (q^2 + 1)$ and $q | (p^2 + 1)$? I can see $13,5$ and $2,5$ has the ...
3
votes
0answers
108 views

What is the value of $\sum_{p\le x} 1/p^2$?

My question is, what is the value of $$\sum_{p\le x} \frac{1}{p^2}?$$ More generally, what is the value of $$\sum_{p\le x} \frac{1}{p^n}?$$ How can we find it? For $\sum_{p\le x} 1/p$ the idea was ...
5
votes
0answers
119 views

Primes as sum of squares.

If $p_{i}$ and $p_{j}$ are two primes of the form $4k+1$ , with $p_{j} > p_{i}$, show that if $p_{j} \neq$ sum of two squares $p_{i}$ is also not equal to sum of two squares. It is well ...
11
votes
1answer
151 views

Is $\sum\frac1{p^{1+ 1/p}}$ divergent?

Is $\displaystyle\sum\frac1{p^{1+ 1/p}}$ divergent? How can we prove that it is divergent or convergent in analytic number theory? I know what bound of the n-th prime number is, and that its order is ...
1
vote
0answers
38 views

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation?

Has anyone established an upper bound for the least integer $k$ such that infinitely many primes have at most $k$ ones in their binary representation? $2$ is the only prime with $1$ one, the Fermat ...
3
votes
2answers
61 views

Cubes differences and primality

In an exercise (Project Euler 131, not to mention it), we are looking for perfect cubes of the form $n^3 + n^2 p$, where p is prime. I finally got the answer by trial and error but I don't understand ...
1
vote
4answers
88 views

Could someone be so kind as to explain this little summation to me?

So basically, the wording in this question, to me, is weird. It goes as follows: Explain why the following formula gives the power $e$ of a given prime $p$ in $n!$: $$e = ...
0
votes
0answers
35 views
+50

Density of primes in a polynomial

Consider that p(x) is a polynomial with integer coeficients. What is the natural density of the below set? $$A = \{n\ |\ p(n)\ is\ prime\}$$ and can we say an statement like prime number theorem ...
3
votes
2answers
52 views

prime division methodology

Trying to solve: Find $a,b,c$ for $31|(5a+7b+11c)$ I found $a=6,b=3,c=1$ as one solution. Is there a systematic way to find all solutions? I was thinking take $5a+7b+11c=31n$ and solve by method ...
-1
votes
2answers
59 views

primes equal if and only if one divides other

$p,q$ primes. prove $p=q$ if and only if $p$ divides $q$. $p|q$ stands for '$p$ divides $q$' $p|q\Leftrightarrow p=q$ $\Leftarrow$: $p(1)=q$ and therefore $p|q$ $\Rightarrow$: if $p=\pm 1$, ...
0
votes
0answers
11 views

What can we say about $\frac{s}{p}$, $\frac{p}{s}$ using these 3 imposed conditions?

What can we say (if anything) about $\frac{s}{p}$ or $\frac{p}{s}$ where $p$ and $s$ are integers greater than $1$ using the following three conditions: $p>s$, $s$ and $p$ are not both divisible ...
0
votes
2answers
43 views

Odd Primes Problem Proof

Given the odd prime numbers, Prove that if $x$ and $y$ are adjacent odd primes in this list, then $x + y$ has $3$ prime factors. The factors need not be distinct. Here is an example I have ...
2
votes
1answer
34 views

How can one show that $\prod_{n<p\leq2n}p\leq C(2n,n)$?

I am trying to rove that $\prod_{n<p\leq2n}p \leq C(2n,n) \leq 2^{2n}$, where $C(2n,n)= \frac{2n!}{n! n!}$ and $p$ is prime. I can prove the second part by induction, but first part induction ...
0
votes
0answers
28 views

proving prime number's divisors

Let p ̸= 0, ±1 be an integer. Prove that p is prime if and only if p satisfies the following property: Whenever a and b are integers such that p = a · b, either a = ±1 or b = ±1. I proved the forward ...
1
vote
3answers
79 views

If $p \mid a^n$ then does $p^n \mid a^n$? [duplicate]

I'm trying to figure out if the statement is true or not and I need to prove it if so. Let $p$ be a prime and $a$ be an integer. If $p\mid a^n$ , is it true that $p^n\mid a^n$ ? I'm not sure how i ...
0
votes
1answer
33 views

Field Characteristic Is Prime…?

Consider the article: http://mathworld.wolfram.com/FieldCharacteristic.html It is stated that given a field and its multiplicative identity $I_{\times}$ that either: $$ \sum_{i=0}^{k}{I_{\times}} ...
0
votes
1answer
51 views

Is it true that in $2^n-1$, when $n$ is a prime number, you don't always get a Mersenne prime?

For $2^n-1$, where $n$ is a prime number, is it true that you don't always get a Mersenne prime? Remember, a Mersenne prime is a number that has a power of two subtracted by one and is then ...
-2
votes
2answers
93 views

All prime numbers bigger than $2$ are either $1$ or $3$ mod $4$ [closed]

How can I prove that each prime number $P \neq 2$ has the form $4n+1$ or $4n+3$ for $n \in \mathbb{N}$?
0
votes
1answer
45 views

Question about Euclid's infinite prime proof

Suppose that $p_1=2 < p_2 = 3 < \cdots < p_r$ are all of the primes. Let $P = p_1p_2...p_r+1$ and let $p_s$ be a prime dividing $P$ where $p_s$ is not in our original list $p_1, p_2, \cdots, ...
1
vote
1answer
44 views

Is there any $k$ such that there are no primes with $k$ digits?

It seems that for any base $b\geq 2$, and for any number of digits $k\geq 2$, there is always some prime number that is $k$ digits long in base $b$. For example, in base $10$, for $2\leq k\leq 10$ we ...
1
vote
1answer
21 views

Necessary and sufficient condition for a number to be regular

Background: A number is said to be (sexagesimally) regular if its reciprocal has a finite sexagesimal expansion (that is, a finite expansion when expressed as a radix fraction for base 60). With the ...
47
votes
10answers
5k views

Why are primes considered to be the “building blocks” of the integers?

I watched the video of Terence Tao on Stephen Colbert the other day (here), and he stated, like many mathematicians do, that the primes are the building blocks of the integers. I've always had ...
0
votes
2answers
53 views

Prime number minus 1 is an even number?

Is it true that for every prime number $p$ (except $p = 2$), that $p-1$ is an even number? I tried it in R (code below) for the first 168 primes (found on wikipedia) and it seems to hold, but I'm not ...
1
vote
1answer
29 views

Question about GIMPS (Great Internet Mersenne Prime Search)

Not sure if this is really an adequate question here, but I found no other place to turn. I'll understand if this gets closed. I recently learned about the GIMPS project, and installed it on my ...
7
votes
2answers
114 views

At least 99% of these numbers are composite

This is from a contest preparation: Prove that at least 99% of these numbers $$10^1+1,10^2+1, 10^3+1, ..., 10^{2010}+1$$ are composite. The problem is from 2010, obviously. I was ...
7
votes
1answer
200 views

Sum of a Sequence of Prime Powers $p^{2n}+p^{2n-1}+\cdots+p+1$ is a Perfect Square

Find all primes p such that $p^{2n}+p^{2n-1}+p^{2n-2}+\cdots+p^{2}+p+1$ is a square for some value of n.
2
votes
0answers
46 views

Find the integral values for which $\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$

Let $\pi(x)$ be the prime counting function. Find all integral values of $x,y$ such that, $$\left(\pi(x+y)\right)^2=4\pi(x)\pi(y)$$ I have no idea as to where to begin with. I think that probably ...
-1
votes
0answers
20 views

Consequences of Cramer's conjecture being false

What if there is an $n_0\in\Bbb N$ such that at almost every $n>n_0$, $$p_{n+1}-p_n=\Omega(p^a)$$ holds with some fixed $a>0$. What are some consequences of this statement in number theory?
2
votes
2answers
78 views

Confusion on the proof that there are “arbitrarily large gaps between successive primes”

I am trying to wrap my brain around a proof that proves that there are arbitrarily large gaps between successive primes. The proof is Given a natural number $N\ge2$, consider the sequence of $N$ ...
3
votes
1answer
58 views

For every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

Prove that for every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$. I have no idea how to prove that.
3
votes
1answer
68 views

Question about $2p-1$ and $2p+1$, where $p$ is a prime.

Let $x+1$ be any prime greater than $3$. By Bertrand's Postulate, there is at least one prime between $\frac{x}{2}$ and $x$. Let $\{p_1,p_2,\dots, p_n\}$ be the primes between $\frac{x}{2}$ and ...
0
votes
0answers
15 views

Estimates for a Mertens-type Product.

The first corollary of Theorem 8 of this paper by Rosser and Schoenfeld states that $$\prod_{p\leq x}\left(\frac{p}{p-1}\right)<e^{\gamma}(\log x)\left(1+\frac{1}{\log^2 x}\right)$$ for all $x\geq ...
2
votes
2answers
60 views

Seven expressions involving $F_n$ an $L_n$ that are always composite

Prove that if $F_n$ an $L_n$ are Fibonacci and Lucas numbers respectively, and $n>2$, then $$F_{n-2}\times F_{n-1}\times F_{n+1}\times F_{n+2}-15$$ $$F_{n-2}\times F_{n-1}\times ...
34
votes
5answers
6k views

If a prime number is reversed, and then appended to itself, why is the result always a composite number?

$2 \Rightarrow 22$ which is a composite number. $37 \Rightarrow 3773$ which is a composite number. $523 \Rightarrow 523325$ which is a composite number. $8123 \Rightarrow 81233218$ which is a ...
3
votes
2answers
187 views

find x where $x^{11} \mod 41 = 10$

In a previous part of the question, I am asked to find $11^{-1} \mod 40$. I've done that, the answer's $11$. The question continues: find $x$ where $x^{11} \mod 41 = 10$ showing how you could get ...
1
vote
2answers
63 views

Is a prime to the power of a fraction always irrational?

Let $p$ be a prime number and let $x$ be a faction, i.e. $x \in \mathbb{Q} - \mathbb{N}$. It seems to be the case that $p^x$ is always irrational. How do I prove this?
15
votes
1answer
177 views

The n-th prime is less than $n^2$?

Let $p_n$ be the n-th prime number, e.g. $p_1=2,p_2=3,p_3=5$. How do I show that for all $n>1$, $p_n<n^2$?
6
votes
1answer
105 views

Prove or disprove that ${F_{n}}^2 + 41$ is always a composite

The problem: Prove or disprove: If $F_{n}$ is the $n^{th}$ Fibonacci number then $${F_{n}}^2 + 41$$ is always a composite number. It looks that if $n$ is not multiple of 12, ${F_{n}}^2 + 41$ ...
6
votes
1answer
95 views

Prove or disprove that ${F_{n}^2} + 43$ is always a composite

This is a kind of follow-up to another question, but in order not to burden that question and its answers with new comments, I decided to create this separate question. Also, it looks this problem is ...
1
vote
0answers
56 views

Riemann's explicit formula for $\pi(x)$

Riemann's explicit formula $J(x)=\mathrm{Li}(x)-\sum_{\Im\varrho>0}\left(\mathrm{Li}(x^\varrho)+\mathrm{Li}(x^{1-\varrho})\right)+\int_x^\infty\frac{\mathrm{d}t}{t(t^2-1)\log t}-\log2,$ where ...
0
votes
1answer
21 views

Show T being prime element in $ F_{2}(T) $

Show that $X^4+TX^2+T$ is irreducible in $ F_{2}(T) $ Using Eisenstein with T as a prime element this proof is simple. Can I proof that T is prime any easier than in the folowing: Theorem 1: K is ...
3
votes
1answer
74 views

Showing irrationality of $\zeta(k)$ for some $k$ without calculating the value.

For $s\in (1,\infty)$ let $\zeta(s):=\sum_{n=1}^\infty \dfrac 1{n^s}$. Is there a way to show that $\zeta(2k)$ is irrational for some integer $k\geq 1$ without finding explicit formulae?
1
vote
1answer
80 views

A question on prime density

Let A = {c > 1 : there exists a natural number m, such that for every n > m, there is a prime between n and cn}. Bertrand's postulate says that A contains 2. My question is : Is inf A = 1 ? If not, ...
32
votes
5answers
647 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$ $${F_{n}}^2 - 28$$ cannot be a prime. I came to this accidentally while trying to solve another ...
-3
votes
0answers
33 views

why are prime numbers important to us today? [duplicate]

Need this for homework. It would be a big help, thanks. I tried the questions some other people posted but they don't have the answer I want.
2
votes
3answers
89 views

Showing that a composite number has a small prime divisor?

At the moment I'm working on proving some statements and I've run into one that I can't seem to wrap my head around. It goes like this: For $n \in \mathbb{Z}^+$, we define $\sqrt{n}$ as the real ...
6
votes
1answer
92 views

What is the least number $n$, such that $n^{2015}+2015$ is prime?

What is the least number $n$, such that $n^{2015}+2015$ is prime ? According to my calculations, there is no prime for $n\le 6000$. It is clear, that $n$ must be even, since $n^{2015}+2015$ must be ...
0
votes
0answers
28 views

questions about probabilistic primality test

As usual I used online Miller-Rabin test,but there's one thing that i don't understand: when i tested 2500 digit or so numbers it only took 1 or few minutes,but there was few numbers that took an ...