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
136
votes
3answers
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 ...
83
votes
20answers
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 ...
27
votes
5answers
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 ...
126
votes
15answers
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$?
34
votes
6answers
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 ...
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{...
35
votes
10answers
10k 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 "...
24
votes
3answers
16k 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,...
13
votes
3answers
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}$$
102
votes
22answers
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 ...
27
votes
8answers
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 ...
5
votes
10answers
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 ...
34
votes
3answers
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 ...
25
votes
5answers
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 ...
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?
67
votes
4answers
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?
26
votes
2answers
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 ...
29
votes
6answers
34k 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,....,...
98
votes
3answers
135k 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
2
votes
1answer
876 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'...
25
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 ...
10
votes
2answers
950 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?
5
votes
1answer
1k 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 ...
17
votes
3answers
14k 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 ...
4
votes
2answers
461 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 ...
1
vote
4answers
235 views

Solve the : $8n+9\equiv 0\pmod{1163}$ , $n\in\mathbb N$

Problem : Solve in $\mathbb N$ : $8n+9\equiv 0\pmod{1163}$ The mathematics give me : $n=435+1163k$ , $k\in\mathbb N$ $1163$ is a prime number $8n\equiv -9\pmod{1163}$ $8n\equiv 1154\pmod{...
8
votes
5answers
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$
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: ...
127
votes
7answers
32k views

Do we have negative prime numbers?

Do we have negative prime numbers? $..., -7, -5, -3, -2, ...$
47
votes
6answers
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 ...
34
votes
7answers
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 ...
33
votes
4answers
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 ...
22
votes
7answers
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.
23
votes
2answers
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?
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 ...
15
votes
2answers
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$...
5
votes
2answers
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?
108
votes
1answer
6k 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 $...
108
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 ...
80
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}$ ...
16
votes
2answers
6k 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 ...
11
votes
3answers
4k 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 ...
9
votes
3answers
1k 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 ...
16
votes
3answers
1k views

Primes dividing a polynomial

Let $g(x)\in \mathbb{Z}[x]$, a nonconstant polynomial. Show that the set of primes $p$ such that $p\mid g(n)$ for some $n\in \mathbb{Z}$ is infinite. I don't know how to start. I have tried asuming ...
18
votes
0answers
1k views

Finding a better approximation to a prime number relation

The basis of this problem, and that which allows for the approximations to be made here, can be summarised in one approximation: $$\Biggl(\frac{n^k -{\lfloor n^{\frac{1}{k}} \rfloor}^{k-1}\gcd({\...
4
votes
2answers
600 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{...
12
votes
2answers
853 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" ...
48
votes
3answers
1k views

Any odd number is of form $a+b$ where $a^2+b^2$ is prime

This conjecture is tested for all odd natural numbers less than $10^8$: If $n>1$ is an odd natural number, then there are natural numbers $a,b$ such that $n=a+b$ and $a^2+b^2\in\mathbb P$. $\...
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 ...
25
votes
2answers
3k 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 ...

1
2 3 4 5
32