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

66
votes
2answers
7k views

The square roots of different primes are linearly independent over the field of rationals

I need to find a way of proving that the square roots of a finite set of different primes are linearly independent over the field of rationals. I've tried to solve the problem using ...
63
votes
11answers
6k views

Why 1 is not considered to be a prime number?

Why $1$ is not considered to be a prime number? Or why definition of prime numbers is given for integers greater than $1$?
26
votes
9answers
6k views

Is there possibly a largest prime number?

Prime numbers are numbers with no factors other than one and itself. Factors of a number are always lower or equal to than a given number; so, the larger the number is, the larger the pool of ...
63
votes
18answers
11k views

Different ways to prove there are infinitely many primes?

This is just a curiosity. I have come across multiple proofs of the fact that there are infinitely many primes, some of them were quite trivial, but some others were really, really fancy. I'll show ...
24
votes
6answers
6k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
20
votes
4answers
11k views

Simple explanation and examples of the Miller-Rabin Primality Test

Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test. Specifically: I understand that for some reason, having non-trivial ...
2
votes
1answer
645 views

If the order divides a prime P then the order is P (or 1)

I've just come up with this question as I'm studying for a number theory midterm. If $p$ and $q$ are different prime numbers, and it's known that $2^p \equiv 1 \bmod{q}$, then $q\equiv 1 \bmod{p}$. ...
20
votes
4answers
4k views

Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

This question relates to a discussion on another message board. Euclid's proof of the infinitude of primes is an indirect proof (a.k.a. proof by contradiction, reductio ad absurdum, modus tollens). My ...
16
votes
2answers
2k views

Can every even integer be expressed as the difference of two primes?

Can every even integer be expressed as the difference of two primes? If so, is there any elementary proof?
86
votes
3answers
3k views

Least prime of the form $38^n+31$

I search the least n such that $$38^n+31$$ is prime. I checked the $n$ upto $3000$ and found none, so the least prime of that form must have more than $4000$ digits. I am content with a probable ...
38
votes
3answers
42k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
24
votes
3answers
2k views

Two Representations of the Prime Counting Function

The bounty for the best work out of Greg's answer, especially the "solving for $\pi^*(x;q,a)$ in terms of all $\Pi^*$ functions (tedious but possible)" part is over. Since Raymond's ...
12
votes
2answers
325 views

Let $p$ be prime and $(\frac{-3}p)=1$. Prove that $p$ is of the form $p=a^2+3b^2$

Let $p$ be prime and $(\frac{-3}p)=1$, where $(\frac{-3}p)$ is Legendre symbol. Prove that $p$ is of the form $p=a^2+3b^2$. My progress: $(\frac{-3}p)=1 \Rightarrow$ ...
10
votes
1answer
3k views

Sum of reciprocal prime numbers

How can the following equation be proven? $$ \forall n > 2 : \sum_{p \le n}{\frac1{p}} = C + \ln\ln n + O\left(\frac1{\ln n}\right), $$ where $p$ is a prime number. It's not homework; I just ...
7
votes
2answers
338 views

Compositeness of $n^4+4^n$ [duplicate]

My coach said that for all positive integers $n$, $n^4+4^n$ is never a prime number. So we memorized this for future use in math competition. But I don't understand why is it?
47
votes
14answers
15k views

For any prime $p > 3$, why is $p^2-1$ always divisible by 24?

I know this is very basic and old hat to many, but I love this question and I am interested in seeing whether there are any proofs beyond the two I already know.
32
votes
6answers
22k views

Is there a known mathematical equation to find the nth prime?

I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
10
votes
2answers
7k views

Help understand the proof of infinitely many primes of the form $4n+3$

This is the proof from the book: Theorem. There are infinitely many primes of the form $4n+3$. Lemma. If $a$ and $b$ are integers, both of the form $4n + 1$, then the product $ab$ is also in ...
5
votes
4answers
2k views

How can we prove that among positive integers any number can have only one prime factorization?

I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
62
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}$ ...
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 ...
84
votes
1answer
4k views

$n!$ is never a perfect square if $n\geq2$. Is there a proof of this that doesn't use Chebyshev's theorem?

If $n\geq2$, then $n!$ is not a perfect square. The proof of this follows easily from Chebyshev's theorem, which states that for any positive integer $n$ there exists a prime strictly between $n$ and ...
33
votes
18answers
46k views

Real-world applications of prime numbers?

I am going through the problems from Project Euler and I notice a strong insistence on Primes and efficient algorithms to compute large primes efficiently. The problems are interesting per se, but I ...
29
votes
6answers
4k views

Percentage of primes among the natural numbers

How high is the percentage of primes in $\mathbb{N}$? ($\mathbb{N} := \lbrace { 1, 2, 3, \ldots \rbrace }$ ; a prime is only divisible by itself and 1 in $\mathbb{N}$) The percentage has to be lower ...
14
votes
4answers
715 views

Prove that $n^2+n+41$ is prime for $n<40$

Here's a problem that showed up on an exam I took, I'm interested in seeing if there are other ways to approach it. Let $n\in\{0,1,...,39\}$. Prove that $n^2+n+41$ is prime. I shall provide my ...
4
votes
3answers
1k views

$p=4n+3$ never has a Decomposition into $2$ Squares, right?

Primes of the form $p=4k+1\;$ have a unique decomposition as sum of squares $p=a^2+b^2$ with $0<a<b\;$, due to Thue's Lemma. Is it correct to say that, primes of the form $p=4n+3$, never have ...
15
votes
4answers
1k views

Proof that there are infinitely many prime numbers starting with a given digit string

To prove the following fact: given any sequence of digits in any base, eg 314159265358979323 base 10, there are infinitely many primes that start with these digits,eg when expressed in decimal they ...
2
votes
2answers
2k views

Prime powers that divide a factorial [duplicate]

If we have some prime $p$ and a natural number $k$, is there a formula for the largest natural number $n_k$ such that $p^{n_k} | k!$. This came up while doing an unrelated homework problem, but it is ...
7
votes
3answers
1k views

Does the sum of reciprocals of primes converge?

Is this series known to converge, and if so, what does it converge to (if known)? Where $p_n$ is prime number $n$, and $p_1 = 2$, $$\sum\limits_{n=1}^\infty \frac{1}{p_n}$$
17
votes
3answers
1k views

How to prove Chebyshev's result: $\sum_{p\leq n} \frac{\log p}{p} \sim\log n $ as $n\to\infty$?

I saw reference to this result of Chebyshev's: $$\sum_{p\leq n} \frac{\log p}{p} \sim \log n \text{ as }n \to \infty,$$ and its relation to the Prime Number Theorem. I'm looking into an ...
12
votes
3answers
426 views

Are there any Combinatoric proofs of Bertrand's postulate?

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and ...
6
votes
1answer
618 views

Summing over General Functions of Primes and an Application to Prime $\zeta$ Function

Along the lines of thought given here, is it in general possible to substitute a summation over a function $f$ of primes like the following: $$ \sum_{p\le x}f(p)=\int_2^x f(t) d(\pi(t))\tag{1} $$ and ...
3
votes
2answers
704 views

Proof of lack of pure prime producing polynomials.

I recently encountered this following proposition: For every polynomial, there is some positive integer for which it is composite. What is the most elementary proof of this?
42
votes
5answers
4k views

What is so interesting about the zeroes of the Riemann $\zeta$ function?

The Riemann $\zeta$ function plays a significant role in number theory and is defined by $$\zeta(s) = \sum_{n=0}^\infty \frac{1}{n^s} \qquad \text{ for } s > 1 \text{ and } s= \sigma + it$$ The ...
12
votes
1answer
677 views

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square

Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square. I tried brute-force method and tried to find some pattern. I got $p=3,7$ as solutions . Apart from these I have tried for ...
25
votes
4answers
4k views

Primes of the form $n^2+1$ - hard?

I met a student that is trying to prove for fun that there are infinitely many primes of the form $n^2+1$. I tried to tell him it's a hard problem, but I lack references. Is there a paper/book ...
7
votes
3answers
698 views

When do the multiples of two primes span all large enough natural numbers?

It is well-known that given two primes $p$ and $q$, $pZ + qZ = Z$ where $Z$ stands for all integers. It seems to me that the set of natural number multiples, i.e. $pN + qN$ also span all natural ...
6
votes
1answer
350 views

Bounds for $n$-th prime

In this Wikipedia page I have found that the bounds for $n$-th prime is given by, $$n(\ln n+\ln \ln n)>p_n>n(\ln n+\ln \ln n-1)$$ for all $n\ge6$. Are there even stronger bounds for the $n$-th ...
3
votes
5answers
2k views

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$
6
votes
4answers
2k views

Alternate definition of prime number

I know the definition of prime number when dealing with integers, but I can't understand why the following definition also works: A prime is a quantity $p$ such that whenever $p$ is a factor of ...
2
votes
1answer
183 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 ...
134
votes
6answers
24k views

Deleting any digit yields a prime… is there a name for this?

My son likes his grilled cheese sandwich cut into various numbers, the number depends on his mood. His mother won't indulge his requests, but I often will. Here is the day he wanted 100: But ...
58
votes
5answers
7k views

Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
18
votes
7answers
5k views

Prime dividing the binomial coefficients

It is quite easy to show that for every prime $p$ and $0<i<p$ we have that $p$ divides the binomial coefficient $\large p\choose i$; one simply notes that in $\large \frac{p!}{i!(p-i)!}$ the ...
18
votes
5answers
4k views

Why is Euler's Totient function always even?

I want to prove why $\phi(n)$ is even for $n>3$. So far I am attempting to split this into 2 cases. Case 1: $n$ is a power of $2$. Hence $n=2^k$. So $\phi(n)=2^k-2^{k-1}$. Clearly that will ...
11
votes
3answers
506 views

$\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges or diverges?

We will denote the set of prime numbers with $\mathcal P$. We know that the sum $\sum_{n=1}^{\infty}\frac1n$ and $\sum_{n=2}^{\infty}\frac1{n\ln n}$ diverges. It is also known that $\sum_{p \in ...
8
votes
1answer
268 views

A little more on $\sqrt[3]{\cos\bigl(\tfrac{2\pi}7\bigr)}+\sqrt[3]{\cos\bigl(\tfrac{4\pi}7\bigr)}+\sqrt[3]{\cos\bigl(\tfrac{8\pi}7\bigr)}$

Using a special case of an identity by Ramanujan, we find that given the roots $x_i$ of $$x^3 + x^2 - (3 n^2 + n)x + n^3=0\tag1$$ which, since its discriminant is negative, always has three real ...
9
votes
3answers
9k views

Infinitely number of primes in the form 4n+1 proof

Question: Are there infinitely many primes of the form 4n+3 and 4n-1? My attempt: Suppose the contrary that there exists finitely many primes of the form 4n+3, say k+1 of them: 3,$p_1,p_2,....,p_k$ ...
12
votes
2answers
690 views

Diophantine equation involving prime numbers : $p^3 - q^5 = (p+q)^2$

Find all pairs of prime nummbers $p,q$ such that $p^3 - q^5 = (p+q)^2$. It's obvious that $p>q$ and $q=2$ doesn't work, then both $p,q$ are odd. Assuming $p = q + 2k$ we conclude, by the equation, ...
12
votes
1answer
600 views

Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $[a,b]$

Consider the closed interval $[0,1]$, there is $\frac{2}{3} \in [0,1]$ where $p=2$ and $q=3$. Similarly consider $[2,3]$, one can have $\frac{5}{2} \in [2,3]$ where $p=5$ and $q=2$. Does every ...