# Tagged Questions

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.

8k 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 ...
8k 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$?
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 ...
7k 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 "...
12k 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 ...
12k 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 ...
17k 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.
658 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}$. I'...
51k 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
3k 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 ...
4k views

352 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?
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 ...
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?
25k 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?
862 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 ...
8k 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 ...
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 ...
19k 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 ...
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?
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 ...
2k 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}$$
1k views

### A theorem about prime divisors of generalized Fermat numbers?

A theorem of Édouard Lucas related to the Fermat numbers states that : Any prime divisor $p$ of $F_n=2^{2^n}+1$ is of the form $p=k\cdot 2^{n+2}+1$ whenever $n$ is greater than one. Does anyone ...
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}$ ...
8k views

### Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
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 information-...
### 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 ...