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

4
votes
1answer
87 views

Binomial theorem for prime exponent

Could you explain to me why for prime $p$ we have the following? $$(x+y)^p - (x^p + y^p)= x^p + \binom{p}{1}x^{p-1}y + \binom{p}{2}x^{p-2}y^2 + \binom{p}{p-1}xy^{p-1} + y^p.$$ I found it here: ...
2
votes
0answers
298 views

Prime numbers with binomial coefficients

Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$ for every $$j\in ...
3
votes
0answers
274 views

Making fermat's little theorem for composite numbers the ultimate test.

It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem ...
5
votes
1answer
106 views

Prime numbers with binomial coefficients

Question: Prove that for any prime $p>3$, the number $\binom{2p-1}{p-1}-1$ is divisible by $p^{3}$. Attempt: Since every integer that is relatively prime to p has a multiplicative inverse modulo ...
1
vote
1answer
123 views

Proof regarding prime numbers:

THEOREM: If a prime $p$ divides a product $a_1 \cdot \cdot \cdot a_n$, then $p$ divides at least one of its factors, $a_i$. This is my attempt at the proof, the book I am reading from suggests ...
1
vote
1answer
71 views

Is there a pair correlation function for primes?

Montgomery's pair correlation function for the non-trivial zeros of the Riemann $\zeta(s)$ function is defined via the term $$1- \left( \frac {\sin(\pi u)}{\pi u} \right)^2$$ Does anybody know if ...
0
votes
2answers
85 views

Is it true that $a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;$?

$$a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;?$$ $p$ prime number and $a,b,k\in\mathbb{N}^+$. And $p$ does not divide $a$. According to Fermat's Little theorem $a^{p-1}\stackrel{p}{\equiv}1$. So ...
4
votes
1answer
174 views

Randomness in prime numbers

I'm very interested in possible randomness in prime numbers distribution. There are many methods for "decomposition" regularity and randomness in primes (e.g. subtraction of some asymptotics , ...
17
votes
4answers
489 views

Do there exist infinitely many pairs of primes $(p,q)$ such that $pq$ divides $2^{p-1}+2^{q-1}-2$?

A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:- Do there exist infinitely many pairs of primes $(p,q)$ such that ...
13
votes
1answer
557 views

Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?

Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, ...
8
votes
3answers
267 views

Number theory: Prime powers and cubes

Determine all triples $(p,a,b)$ of positive integers, where $p$ is prime and $a \leq b$ such that $$p^a+p^b$$ is a perfect cube. I came across this question while looking at past maths Olympiad ...
0
votes
2answers
748 views

GCD and LCM using Prime Factorization

I saw in a book that we can find the LCM and GCD of three numbers using prime factorization . That was really cool :) I'll explain what i saw and will let you know my doubt in the end! Three numbers ...
16
votes
6answers
1k views

Prove $a+b+c+d $ is composite

Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite. I have my own solution for this (As posted) and i want to see if there is any other good proofs.
3
votes
1answer
202 views

Average of divisors of n.

Let n be a natural number and let $f(n)=\frac{\sigma(n)}{d(n)}$ be the arithmetical average of n's divisors. Either prove or give a counterexample that for all natural numbers like n, which are not ...
3
votes
2answers
689 views

Prove by mathematical induction for any prime number$ p > 3, p^2 - 1$ is divisible by $3$?

Prove by mathematical induction for any prime number $p > 3, p^2 - 1$ is divisible by $3$? Actually the above expression is divisible by $3,4,6,8,12$ and $24$. I have proved the divisibility by ...
1
vote
0answers
68 views

Consequencesof the Hadamard product expression of $L(s, \chi)$

I'm going through my lecture notes and I'm stuck on the proof of For any $t>0$ and primitive $\chi$ modulo $q$ $$\sum_{\rho=\beta+i \gamma: \Lambda(\rho, ...
5
votes
1answer
98 views

Constraints on $x$ such that $2x+1$ is prime

I have read quite a bit about prime numbers recently (having just started a module on elementary number theory, groups, primes, etc.), and something that always seems to be popping up is powers of 2. ...
31
votes
6answers
6k views

Are all prime numbers finite?

If we answer false, then there must be an infinite prime number. But infinity is not a number and we have a contradiction. If we answer true, then there must be a greatest prime number. But Euclid ...
1
vote
0answers
203 views

Fourier Analysis of Prime Counting Function

I was thinking about the following: Denote $\pi(x)$ as the prime counting function such that: $$ \pi(x) = \#\text{ of prime numbers}\leq x $$ It is well known from the prime number theorem that $$ ...
1
vote
1answer
203 views

Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number

Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number. If true (which I'm pretty sure it isn't), then the proof needs to be in either contradiction or ...
5
votes
1answer
122 views

Does this have a name: If an odd prime $p$ does not divide $a$, then $p$ divides $a^n + 1$ or $a^n - 1$

After seeing and doing a bunch of proofs like "For all $a$ in the natural numbers, then if $7$ does not divide $a$, then $7$ divides $a^3+1$ or $a^3-1$," I conjectured the following, but got stuck in ...
1
vote
1answer
89 views

Research on $\log(p)$? [closed]

We are searching for articles, research work or interesting interpretations/applications of $\log(p)$ where $p$ a prime. It should not be only limited to math, contributions from physics are also ...
2
votes
1answer
452 views

Euler's totient function maximum value for a range [duplicate]

For the euler's totient function, we have a number $n<10^{18}$ we have to find the value of $i$ between $2$ and $n$ (both inclusive) such that the value of $\phi(i)/i$ is maximum. I have have ...
6
votes
1answer
301 views

Hamlet to be or not to be in Primes?

It is conjectured that, if you read $\pi$ long enough you'll find Hamlet. Since other numbers, like the Copeland–Erdős constant are known to be normal in base $10$, it should be true at least there. I ...
3
votes
1answer
424 views

What software can calculate the order of $b \mod p$, where $p$ is a large prime?

I wasn't sure where to ask this, but Mathematics seems better than StackOverflow or Programmers. I have no background whatsoever in number theory, and I need to find software that can calculate the ...
23
votes
1answer
357 views

Is any closed-form representation known for the sum $\sum\limits_{n=1}^{\infty}\frac{\mu(n)\log n}{n^2}$?

Is any closed-form representation known for the sum $\sum\limits_{n=1}^{\infty}\frac{\mu(n)\log n}{n^2}$, where $\mu(n)$ is the Möbius $\mu$-function?
3
votes
2answers
173 views

A question about the Andrica's conjecture on the prime numbers

The Andrica's conjecture on the prime numbers states: given a couple of prime numbers $p_k$ and $p_{k+1}$ the following inequality holds: $$\sqrt{p_{k+1}}-\sqrt{p_{k}}\lt 1$$ Is it possible to show ...
12
votes
1answer
416 views

Prove that $\sum\limits_{i=0}^{k} p^{2i}$ ($p$ is prime) is never a perfect square

Prove that $$ \sum_{i=0}^{k} p^{2i} $$ where $k > 0$ and $p$ is an arbitrary prime, is never a perfect square. I think you can prove it by letting $q = \sum\limits_{i=0}^k a_ip^i$, then expanding ...
1
vote
1answer
85 views

Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?

If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
4
votes
2answers
143 views

Let $m^n-1$ be prime. What can $m$ be?

Let $m^n-1$ be prime. What can $m$ be if $m$ and $n$ are not $1$? How can I find $m$?
5
votes
1answer
358 views

Is this number theory conjecture known to be true?

I've been working on proving that there is always a prime between $n$ and $2n$, and also that there is always a prime between $n^2$ and $(n+1)^2$ (Legendre's conjecture). I believe I've proven those ...
7
votes
3answers
180 views

Finding a prime number between $n$ and $2n$

I am trying to find a prime number between $n$ and $2n$. I know that the number of primes between $n$ and $2n$ is $n/(2\ln n)$. I was thinking of choosing a random number between $n$ and $2n$ and ...
0
votes
1answer
155 views

Smallest Mersenne prime with 100 million digits?

As some of you are probably aware, the Great Internet Mersenne Prime Search (GIMPS) is managing the search for the largest Mersenne primes of the form $M_p=2^p-1$, where $p$ is itself prime (GIMPS ...
2
votes
1answer
646 views

Understanding the pseudocode for the Sieve of Eratosthenes

The outer loop on the Wikipedia page for the Sieve of Eratosthenes ends at √n: for i = 2, 3, 4, ..., √n : Is this because if n has a square root it wont be prime? From what I understand this ...
9
votes
3answers
703 views

Size of largest prime factor

It is well known and easy to prove that the smallest prime factor of an integer $n$ is at most equal to $\sqrt n$. What can be said about the largest prime factor of $n$, denoted by $P_1(n)$? In ...
2
votes
3answers
67 views

Does there exist a k such that the kth prime is balanced in order k-1?

A balanced prime of order n is a prime number that is equal to the arithmetic mean of the nearest n primes above and below. For example, 5 is a balanced prime in order 1 because it is the average of ...
6
votes
2answers
70 views

Need to state “$p$ not equal to $61$” when solving $61p + 1 = n^2$?

In the pictures below, am I wrong to say that the 3 lines in the red box are not needed in the solutions? Regardless of whether 61 and p are distinct, it's still true that we have only the 2 possible ...
0
votes
1answer
109 views

Find if a number $n$ is a primitive root of $p$

Let $n = p_1\cdot p_2\cdot\ldots\cdot p_k$ where the $p_i$ are primes. Let $s = \varphi(n)$ where $\varphi$ denotes the Euler Totient Function. If none of $p_1,p_2,\ldots,p_k$ makes $a^{(s/p_i)} = 1$ ...
3
votes
3answers
366 views

Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)

Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which ...
2
votes
2answers
336 views

Miller-Rabin Primality Test

I am trying to work out the potential primality of 341 using the Miller-Rabin algorithm. Below is as far as I get, I'm not really sure where to go from there. I believe I am supposed to use modular ...
19
votes
2answers
12k views

Has anyone found a “pattern” in prime numbers?

Yesterday I was having some fun trying to look for some patterns in primes; and I think I found something interesting (to me at least). I still have not found any lists of patterns already found, ...
5
votes
2answers
321 views

Integer solutions of $n^3 = p^2 - p - 1$

Find all integer solutions of the equation, $n^3 = p^2 - p - 1$, where p is prime.
1
vote
3answers
127 views

Prime number characterisation using congruences

I want to prove that $n$ is prime. From the Wilson's theorem it follows that $n$ is prime if and only if $$(n-1)! + 1 \equiv 0 \pmod{n}$$ However, in my proof, I reduce the congruences to the ...
-2
votes
2answers
372 views

How to quickly check if a number is prime? [closed]

Let say I've found a very very very long prime number. I know it's prime but I need to have a proof. Is there any fast way how to check if a number is really prime? Let say I've found the longest ...
5
votes
1answer
146 views

Understanding a famous proof by Jitsuro Nagura: Need help understanding one step in the main theorem

I am going through the proof by Jitsuro Nagura which shows that there is always a prime between $x$ and $\frac{6x}{5}$ where $x \ge 25$. Nagura uses the following definitions: $$\vartheta(x) = ...
3
votes
1answer
157 views

Is my proof correct? $p_1p_2p_3\cdots p_n+1)$ cannot be the square of an integer

Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer. Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so ...
1
vote
2answers
157 views

Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)

I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-hellman key exchange? Any help would be appreciated :) this is a link to a previous post which quickly ...
5
votes
2answers
269 views

Prime numbers, what explains this pattern?

This morning I got a message on the Active Mathematica yahoo mailing list from the signature "in zero" asking to calculate this sum: $$\sum _{k=1}^n \frac{\log (p_k)}{\log (p_n)}$$ where $p_n$ is ...
3
votes
2answers
568 views

Factorial primes

Factorial primes are primes of the form $n!\pm1$. (In this application I'm interested specifically in $n!+1$ but any answer is likely to apply to both forms.) It seems hard to prove that there are ...
2
votes
3answers
392 views

About linear combinations of primes

$a,b,c$ are natural numbers whose greatest common divisor is $1$. $a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$ Try to write down the expression using $a,b,c$ of the biggest natural number $M$ that cannot be ...