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.

Filter by
Sorted by
Tagged with
127
votes
3answers
15k 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 ...
73
votes
16answers
41k 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.
114
votes
14answers
58k 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$?
18
votes
2answers
1k 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$ $(\frac{-3}p)=(\frac{-1}p)(\frac{...
25
votes
5answers
19k 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 ...
33
votes
6answers
11k 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 ...
32
votes
10answers
9k 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 "...
11
votes
3answers
5k 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}$$
5
votes
9answers
914 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 ...
2
votes
4answers
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?
25
votes
8answers
10k 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 ...
83
votes
3answers
119k 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
93
votes
22answers
18k 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 ...
30
votes
3answers
4k 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 ...
23
votes
5answers
5k 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 ...
23
votes
3answers
11k views

If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

The proof is already given in the textbook but I tried other way around. Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So $\gcd(p,...
21
votes
2answers
7k 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 ...
5
votes
1answer
875 views

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

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 divids m, doesn't have any answer and its proof can be obtained ...
2
votes
1answer
814 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'...
14
votes
2answers
13k 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 this ...
59
votes
4answers
45k 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?
27
votes
6answers
28k 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 exist finitely many primes of the form $4n+3$, say $k+1$ of them: $3,p_1,p_2,....,...
30
votes
7answers
16k 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 ...
23
votes
4answers
3k 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 ...
7
votes
5answers
10k 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$
61
votes
11answers
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: ...
10
votes
5answers
3k views

The Frobenius Coin Problem

I am asked to prove that: For integers $n, x,y > 0$, where $x,y$ are relatively prime, every $n \ge (x-1) (y-1)$ can be expressed as $xa + yb$, with nonnegative integers $a,b \ge0$. ...
5
votes
3answers
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 ...
103
votes
1answer
5k 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 $...
102
votes
3answers
4k 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 ...
20
votes
7answers
4k 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.
11
votes
3answers
3k 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 ...
4
votes
2answers
363 views

$(p\!-\!1\!-\!h)!\,h! \equiv (-1)^{h+1}\!\!\pmod{\! p}\,$ [Wilson Reflection Formula]

Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$. I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$ My first thought is that by ...
76
votes
9answers
10k 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}$ ...
112
votes
7answers
25k views

Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
33
votes
4answers
11k 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 ...
21
votes
3answers
4k 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?
14
votes
1answer
4k 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 ...
12
votes
1answer
9k 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$...
10
votes
2answers
751 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?
4
votes
2answers
506 views

Is there a way to show that $\sqrt{p_{n}} < n$?

Is there a way to show that $\sqrt{p_{n}} < n$? In this article, I show that $f_{2}(x)=\frac{x}{ln(x)} - \sqrt{x}$ is ascending, for $\forall x\geq e^{2}$. As a result, $\forall n \geq 3$ $$\frac{...
11
votes
2answers
757 views

Currently, what is the largest publicly known prime number such that all prime numbers less than it are known?

So recently, an absurdly large prime number was found, but a lot of prime numbers less than it are still not known. I am wondering up to where we know all the primes. I put "currently publicly known" ...
4
votes
2answers
2k 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?
39
votes
2answers
26k 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 ...
44
votes
5answers
7k 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 ...
38
votes
8answers
12k views

How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4?

It is a theorem in elementary number theory that if $p$ is a prime and congruent to 1 mod 4, then it is the sum of two squares. Apparently there is a trick involving arithmetic in the gaussian ...
19
votes
4answers
4k 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 ...
38
votes
14answers
4k views

Is the number $-1$ prime?

From my understanding it's not prime because it's not greater than $0$. So my followup question is why did mathematicians exclude $-1$? The definition of prime is having only two factors. $-1 \cdot ...
14
votes
3answers
638 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 $...
14
votes
2answers
4k 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 ...