# Questions tagged [prime-numbers]

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.

1,591 questions
Filter by
Sorted by
Tagged with
18k 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 elementary ...
53k views

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

Let $p>3$ be a prime. Prove that $24 \mid p^2-1$. 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 ...
20k views

### Split $n$ into nontrivial factors via a nontrivial square-root of $1\!\pmod{\!n}$

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 ...
71k views

### Why is 1 not a prime number?

Why is $1$ not considered a prime number? Or, why is the definition of prime numbers given for integers greater than $1$?
13k 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 ...
1k views

6k 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}$$
19k 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 ...
12k 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 ...
1k views

### If a prime $p\mid ab$, then $p\mid a$ or $p\mid b$

If a prime number $p$ is a divisor of a product $ab$, $p$ has to be a divisor of $b$ or $a$. How can I demonstrate this theorem? I demonstrated this theorem on one way using Bezout's theorem in an ...
5k 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 ...
6k 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 ...
4k views

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

I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
50k 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?
9k views

### Probability that two random numbers are coprime is $\frac{6}{\pi^2}$

This is a really natural question for which I know a stunning solution. So I admit I have a solution, however I would like to see if anybody will come up with something different. The question is ...
34k views

13k views

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

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$
17k views

### Why is Euclid's proof on the infinitude of primes considered a proof?

I've expressed Euclid's proof on the infinitude of primes on Mathematica: ...
32k views

### Do we have negative prime numbers?

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

### I'm trying to find the longest consecutive set of composite numbers

Hello and I'm quite new to Math SE. I am trying to find the largest consecutive sequence of composite numbers. The largest I know is: $$90, 91, 92, 93, 94, 95, 96$$ I can't make this series any ...
20k 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 ...
13k 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 ...
5k views

### Is that true that all the prime numbers are of the form $6m \pm 1$?

Is that true that all the prime numbers are of the form $6m \pm 1$ ? If so, can you please provide an example? Thanks in advance.
5k 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?
2k 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 ...
11k views

### Proof for: $(a+b)^{p} \equiv a^p + b^p \pmod p$

a, b are integers. p is prime. I want to prove: $(a+b)^{p} \equiv a^p + b^p \pmod p$ I know about Fermat's little theorem, but I still can't get it I know this is valid: $(a+b)^{p} \equiv a+b \pmod p$...
3k views

### Proof of lack of pure prime producing polynomials. [duplicate]

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?
6k views

### least common multiple $\lim\sqrt[n]{[1,2,\dotsc,n]}=e$
The least common multiple of $1,2,\dotsc,n$ is $[1,2,\dotsc,n]$, then $$\lim_{n\to\infty}\sqrt[n]{[1,2,\dotsc,n]}=e$$ we can show this by prime number theorem, but I don't know how to start I had ...