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.

learn more… | top users | synonyms

3
votes
1answer
123 views

Can we replace the upper limit condition of the Sieve of Eratosthenes $\sqrt{n}$ with the value $\sqrt{p}$ where $p$ is the last sieved prime $\lt n$?

By chance I stumbled upon the OEIS list A033677 of the smallest divisor of $n$ greater or equal to $\sqrt{n}$. Roughly speaking if we use the classic enhanced sieve of Eratosthenes, $\sqrt{n}$ is the ...
1
vote
1answer
49 views

How many numbers $m$ satisfy $1 ≤ m ≤ n$ and $\gcd (m, n) = 1$?

Let $n = p^2 q$ where $p$ and $q$ are distinct prime numbers. How many numbers $m$ satisfy $1 \leq m \leq n$ and $\gcd (m, n) = 1$? Note that $\gcd (m, n)$ is the greatest common divisor of $m$ and ...
0
votes
0answers
39 views

How to generate the sequence of prime building blocks of the colossally abundant numbers: $2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 23, 2,…$

This is the sequence of prime numbers which are the elementary building blocks for the superior highly composite numbers: $2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 2, 23, 7, 29, 3, 31, 2, 37, ...
4
votes
0answers
60 views

Is there a relationship between local prime gaps and cyclical graphs?

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial ...
1
vote
1answer
51 views

For which odd primes $p ≠ 5$ is 10 a qudratic residue modulo $p$?

For which odd primes $p ≠ 5$ is 10 a quadratic residue modulo $p$? Saw a similar example using 5 and 15 and did my best to learn from those but still having a hard time grasping how to complete this ...
5
votes
0answers
34 views

What percentage of prime number factorials plus 1 are themselves prime?

One of the steps in Euclid's proof of the infinity of primes is sometimes misinterpreted to be a way of generating new prime numbers. Specifically constructing the number P!+1 where P is a prime is ...
0
votes
2answers
29 views

Integer Logic - Relatively Prime Numbers Proof

I could use some help understanding this. Let a,b,c ∈ Z. Suppose that (a,c) = (b,c) = 1. Prove that (ab,c) = 1. I assume that there exist some x, y ∈ Z where (ab,c) = 1 such that abx + yc = 1. ...
3
votes
1answer
31 views

If $K \subset \mathbb{Q}(\sqrt[p]{2},\sqrt[q]{2})$ and $[K : \mathbb{Q}]=p$ then $K= \mathbb{Q}(\sqrt[p]{2})$

Let $p,q$ be distinct prime numbers and assume that $p<q$. Prove that if a subfield $K \subset \mathbb{Q}(\sqrt[p]{2},\sqrt[q]{2})$ satisfies $[K : \mathbb{Q}]=p$, then $K= ...
3
votes
1answer
47 views

Verifying a step in the prime number theorem

This is an excerpt from Shapiro, "Introduction to the theory of numbers": Suppose that we have an estimate of the form $$|R(x)|\le \alpha x$$ valid for all sufficiently large $x$ (say $x\ge x_2$). ...
0
votes
1answer
34 views

Let $p$ be and odd prime. Use Wilson's Theorem to show that…

Let $p$ be and odd prime. Use Wilson's Theorem to show that: $[(\frac{p -1}{2}) !]^2$ $\equiv$ $(-1)^{(p+1)/2}$ mod $p$ My understanding is that this should be as simple as picking an odd prime and ...
1
vote
2answers
31 views

Find all positive integers $n$ such that $n$,$n + 2$, and $n + 4$ are all primes…

Find all positive integers $n$ such that $n$,$n + 2$, and $n + 4$ are all primes. Having a tough time with this problem, I feel that brute force is a possibility especially considering that my ...
1
vote
4answers
65 views

Find all pairs of prime numbers $p, q$ such that $p+q = 18(p−q)$.

Find all pairs of prime numbers $p, q$ such that $p+q = 18(p−q)$. It is clear that $p-q$ must be an even number since if we consider $q$ as $2$, we won't get any solution. So any pair of odd prime ...
5
votes
2answers
86 views

Proving that $\pi(2x) < 2 \pi(x) $

In our analytic number theory class we were given the following problem as homework: prove rigorously that for large $x$ the number of primes in $(1,x]$ exceeds that in $(x,2x]$. In class we proved ...
0
votes
1answer
55 views

A Mersenne prime has $17 425 170$ digits. How many digits need to be checked to know that this is a prime?

A Mersenne prime has $17 425 170$ digits. How many digits needs to be checked to know that this is a prime? I know that the square rot of a number digit needs to be checked to know if it is a prime, ...
3
votes
4answers
176 views

Storing a natural number as a set of its Nth prime factors, how much data is used?

Spoiler, tap to reveal. In asking the following question, I knew that each natural number could be prime factorised. However I assumed that most natural numbers would each be equal to the ...
11
votes
1answer
585 views

odd prime division

Prove that if $p$ is an odd prime then $p$ divides $\lfloor(2+\sqrt5)^p\rfloor -2^{p+1}$ I am struggling to progress with this question. Here is my working out so far: Page 1 working out Page 2 ...
19
votes
0answers
525 views

Divergence of the Derivative of the Prime Counting Function

On the one hand, the Prime Counting Function $\pi_0(x)$ maybe be written $$ \pi_0(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho}) \tag{1} $$ with $ \operatorname{R}(z) = ...
0
votes
3answers
190 views

What is the definition of prime number?

Every number has the factors of $1$, itself, $-1$, and the negative version of itself (itself multiplied by $-1$). So let's take for example $5$, it has the factors: $ 1$ $ 5$ $-1$ $-5$ ...
14
votes
1answer
231 views

Twin Primes (continued research)

This has become increasingly crowded, so at the onset, let me state this: My question is, is there some reason this is so linear that I'm not seeing? The only thing it seems to indicate to me is that ...
15
votes
2answers
259 views

Primes of form $a^2 + 24b^2$

For a prime number $p \neq 2$, $3$, is it necessarily the case the prime number can be written in the form $a^2 + 24b^2$ if and only if $p \equiv 1 \text{ mod }24$? I think this has to be true based ...
6
votes
5answers
1k views

What's problematic about finding out if a large number is Prime or not?

I was reading somewhere that it's hard to determine if a number is prime or not if it gets too large. If I understand correctly, all numbers can be broken into prime factors. And numbers which can't ...
0
votes
1answer
229 views

Prove that $a$ is a primitive root $\bmod{p}$ if and only if $-a$ has order $\frac{p-1}{2}$

Consider a prime $p$ $\in\mathbb{N}$ of the form $4t+3$, with $t$ $\in\mathbb{N}$. Prove that a $\in\mathbb{Z}$ is a primitive root $\mod p$ if and only if $-a$ has order $\frac{(p-1)}{2}$. I showed ...
9
votes
1answer
1k views

Why are there so many primes in the convergents of Pi?

Recently, I was looking into fractional approximations of pi, such as $\frac{22}{7}$ or $\frac{355}{113}$. I found that there was a name for these approximations, 'convergents' of pi, and I found a ...
19
votes
2answers
421 views

Sum of reciprocals of primes factorial: $\sum_{p\;\text{prime}}\frac{1}{p!}$

The series $$\sum_{p\;\text{prime}}\frac{1}{p}=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\cdots$$ diverges as is well known. How about the following? ...
0
votes
1answer
32 views

Bound for number of distinct prime divisors (don't understand the proof)

The task is to determine a bound for the number of distinct prime divisors. The proof can be found here: The smallest number with $k$ distinct prime divisors is the $k^\text{th}$ primorial. So the ...
0
votes
1answer
88 views

Count numbers with prime digit

Given a number $N$, I need to find the count of the numbers that have atleast one prime digit $2,3,5$ or $7$ in it. Now $N$ can be upto $10^{18}$. What is the best approach to solve this problem. ...
0
votes
1answer
43 views

For every odd $n \in \mathbb{N}$ prove that $\phi(n)$ is not equal $2^{32}$ [duplicate]

I have a question: I proved that If $n \in \mathbb{N}$ is an odd number and $\phi(n)$ is a power of $2$ then $n$ is a product of distinct primes. Now I need to prove that for every odd $n \in ...
0
votes
0answers
23 views

Cauchy's theorem spin-off

In group theory we know from Cauchy's theorem that any finite group of order n has at least one subgroup of order p, if p|n. How can we prove the following statement: "If G is a finite group of order ...
0
votes
2answers
40 views

If $b$ is an odd composite number and $\dfrac{b^2 - 1}{\sigma(b^2) - b^2} = q$ is a prime number, what happens when $q = 2^{r + 1} - 1$?

(Note: An improved version of this question has been cross-posted to MO.) Let $\sigma(X)$ be the sum of the divisors of $X$. For example, $\sigma(2) = 1 + 2 = 3$, and $\sigma(4) = 1 + 2 + 4 = 7$. ...
8
votes
2answers
532 views

Does a finite sum of distinct prime reciprocals always give an irreducible fraction?

If we add any finite number of any distinct prime reciprocals, will the result always be an irreducible fraction? If not, is there any bound on the value of a greatest common divisor for the ...
2
votes
1answer
41 views

An odd positive integer is the product of $n$ distinct primes. In how many ways can it be represented as the difference of two squares?

An odd positive integer is the product of $n$ distinct primes. In how many ways can it be represented as the difference of two squares? My formulation of the question: $$x^2 - y^2 = ...
1
vote
0answers
21 views

On the roots of certain functional inequality

I have a question to share, if someone can help me. Let, for each prime $n>2$ $L_{n}:[0,+\infty)\longrightarrow \mathbb{R}$ the function given by $ ...
0
votes
1answer
28 views

A problem regarding polynomials with prime values

The problem is as follows: Prove that there is no non-constant polynomial $P(x)$ with integer coefficients such that $P(n)$ is a prime number for all positive integers $n$. I cannot solve it. I ...
1
vote
1answer
24 views

Showing $\psi(x)=\theta(x)+O(\sqrt x\log x)$ for Chebyshev's function $\psi$

In my textbook, there is the following theorem: For all $x>0$, we have $$\psi(x)=\sum_{\alpha=1}^\infty\theta(x^{1/\alpha})$$ and hence $$\psi(x)=\theta(x)+O(\sqrt x\log x).$$ Here ...
1
vote
1answer
56 views

Compositeness test for repunits

Is this proof acceptable ? Definition Let $R_p=\frac{10^p-1}{9} $ with $p$ prime be a repunit number . Theorem If $R_p$ is prime then $7^{\frac{R_p-1}{2}} \equiv -1 \pmod {R_p}$ Proof Let $R_p$ ...
0
votes
0answers
23 views

An exponential sum problem.

If $q$ is a prime how do we compute $$\sum_{a,b,c\mod q} I_{1/4,\epsilon}(a)I_{1/4,\epsilon}(b)I_{1/2,\epsilon}(c)I_{1/2,\epsilon}(ca^{-1}b)I_{1/2,\epsilon}(cab^{-1})$$ where $I_{a,\epsilon}(x)=1$ if ...
1
vote
0answers
22 views

Pocklington-Lehmer primality test

I have a question to the Pocklington-Lehmer criterion for primality testing which is commonly stated as follows: Let $n\in\mathbb{N}$ s.t. $n-1=a\cdot b$ where $a>\sqrt{n}$ and $a,b$ are coprime. ...
21
votes
6answers
4k views

Understanding Euclid's proof that the number of primes is infinite. [duplicate]

In Euclid's proof, if $p_1, p_2, \dots, p_n$ are the only primes then $p_1 \times p_2 \times \dots \times p_n + 1$ is not divisible by any of $p_1, p_2, \dots, p_n$ (because of some algebraic facts), ...
0
votes
2answers
2k views

Proof — Infinitely many primes of the form $4k + 3$ — origin of $4(p_1…p_k - 1) + 3$

I know there are sundry questions — like this pdf — and this (10.) Prove that any positive integer of the form $4k + 3$ must have a prime factor of the same form. Because $4k + 3 = 2(2k + 1) + 1$, ...
0
votes
0answers
17 views

Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3? [duplicate]

Prove that the product of the primitive roots modulo the prime p is congruent to 1 modulo p if p > 3. Just started going over primitive roots in class and a bit lost with this question. I do know ...
15
votes
5answers
4k views

Proving that there are infinitely many primes with remainder of 2 when divided by 3

I need to prove that there are infinitely many primes with remainder of 2 when divided by 3. I started out similarly to Euclid's classic proof of an infinite number of prime numbers: Suppose there is ...
2
votes
1answer
55 views

Probability of prime numbers

Say we use the Euclidean construction for prime numbers and take a set $S$ solely containing prime numbers, so that $p_n$ is the greatest prime within S. What is the probability that $1+p_1 \cdots ...
3
votes
0answers
29 views

Recreational math dealing with twin primes

This is kinda recreational math with a goal in mind of progressing further toward a proof of the twin prime conjecture. Consider this: We start with a random prime: $109$ $3*109=327$ $327 ...
4
votes
7answers
1k views

Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
2
votes
0answers
37 views

A very nice pattern involving prime factorization

A while ago I was fiddling around with prime numbers and C++. I defined: $$f_a(b)= \text{ the amount of numbers } 2^a\leq n<2^{a+1}\text{ with } b \text{ prime factors}$$ I calculated $f_a(b)$ for ...
6
votes
2answers
88 views

example, that Wilson's Theorem is not necessarily true

Show by an example, that Wilson's Theorem is not necessarily true if $p$ is not prime. (In fact, it is not hard to show that it is never true if $p$ is not prime, but I am not asking you to do that.) ...
0
votes
1answer
31 views

Show, using the rational root test, that $\sqrt{p}$ is irrational, for any positive prime $p$.

Show, using the rational root test, that $\sqrt{p}$ is irrational, for any positive prime $p$. The lecturer specifically asks that he wants us to show the above question, through showing that ...
3
votes
0answers
70 views

How close are we to knowing the rate of convergence to $0$ of $\prod_{p\le x}(1-1/p)^{-1}-e^\gamma\log x $?

This is a question related to an earlier one of mine, which I may answer myself eventually, as I have learnt more about the topic. Despite what one can read on the MathWorld page about Mertens' third ...
0
votes
1answer
31 views

Find a prime $p>5$ such that $x^2 +1$ is reducible in $\mathbb Z_p[x]$

Find a prime $p>5$ such that $x^2 +1$ is reducible in $\mathbb Z_p[x]$. Can anyone please give me some hints as to how I can go about finding this value of $p$?
0
votes
1answer
48 views

Primality testing though trial division.

I am having difficulty to understand this statement mentioned here: Remember that any composite integer n is build out of two or more primes n = P * P … P is largest when n has exactly two ...