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

1
vote
1answer
63 views

What is the percentage of prime numbers among all numbers with 100 decimal digits?

I know the Prime Number Theorem, but 100 digits numbers are too big to be put in a calculator. Is there a way of finding out how many primes numbers as a percentage of the total numbers with 100 ...
1
vote
1answer
37 views

The exponent of $11$ in the prime factorization of $ 300!$ is___.

The exponent of $11$ in the prime factorization of $ 300!$ is $27$ $28$ $29$ $30$ My attempt: According to Exponent of $p$ in the prime factorization of $n!$ ...
2
votes
2answers
54 views

Natural numbers sorted uncountable?

$|\mathbb{N}|$ by definition is countable infinite. Going to sets of elements indexed by a finite number of indices labelling countable components yields again countably infinite sets (like when ...
3
votes
1answer
69 views

Sum of products of $(1 - 1/p)$

Let $\pi(n)$ denote the number of primes not greater than $n$, and $p_k$ the $k$th prime, so that $p_{\pi(n)}$ denotes the largest prime not greater than $n$. I'm interested in the value of the ...
0
votes
1answer
39 views

Prime numbers sum (interchanged digits)

Here is a question which is really troublesome: Let N be a 2 digit prime number. When the digits are interchanged we get another prime number M. If M + N =176, find N-M.
4
votes
3answers
59 views

Quick, self-contained way to see why $\left({{-1}\over p}\right) = 1$?

Let $p$ be a prime number congruent to $1$ modulo $4$. What is a quick and self-contained way to see why$$\left({{-1}\over p}\right) = 1?$$
5
votes
4answers
64 views

$R = \mathbb{Z}[\sqrt{-41}]$, show that 3 is irreducible but not prime in $R$

I'm asked to show that 3 is irreducible but not prime in $R = \mathbb{Z}[\sqrt{-41}]$. And if $R$ is a Euclidean domain. To show that it's not prime I have $(1 + \sqrt{-41})(1 - \sqrt{-41}) = 42 = ...
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, ...
1
vote
1answer
50 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 ...
1
vote
1answer
48 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 ...
3
votes
1answer
30 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= ...
0
votes
1answer
30 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 ...
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
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$). ...
1
vote
4answers
60 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
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
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
2answers
84 views

Prove that the value of the constant $C$ must be $1$

After proving the prime number theorem in class, our professor directs us to a remark by Lagrange that for large values of $x$, $\pi(x)$ is approximately equal to $$ \frac{x}{\log x - B}. $$ (This is ...
5
votes
2answers
83 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 ...
3
votes
1answer
122 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 ...
6
votes
5answers
990 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 ...
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 ...
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
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 ...
9
votes
1answer
217 views

How many numbers $ N \le 10^{10}$ are the product of $3$ distinct primes?

How many numbers $ N \le10^{10}$ are the product of $3$ distinct primes? I can realistically calculate any $\pi(n), n < 10^{15} $ but I don't think it's possible to list all primes $>10^8$ in ...
3
votes
0answers
271 views

The Divisors of $s(2s+1)$ and Primes $2n+1$ and $3n+1$ part 1

I want to check my math (and proof) on the following claim. The claim is by way of a computer search and a "hunch". claim: If $s$ is a prime number I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be ...
2
votes
1answer
38 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
20 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 $ ...
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 ...
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
41 views

Primality testing vs sieve

If the goal is to decompose an integer into its prime factors, is it better to use a sieve (such as the Sieve of Eratosthenes) or trial division up to the square root? Wikipedia has the statement ...
1
vote
1answer
23 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 ...
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. ...
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 ...
2
votes
1answer
54 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 ...
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 ...
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), ...
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 ...
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
28 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 ...
0
votes
1answer
29 views

Totien-Sum: why GCD( {n}/d, q/d) = 1; implies Sum{Totient(d/q) } = q

Have seen answer to this question. still don't understand.. Totient sum is defined: q = Sum(Totient (d) ); sum on all d : d|q More specific; The proof has these steps: 1. If d is a divider ...
0
votes
1answer
46 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 ...
3
votes
2answers
34 views

How can I prove that a linear recurrence $x_{n+1} = αx_n - β$ will contain a composite number in the sequence?

I'm working on a homework problem about finite automata and I got stuck trying to prove a fact about prime numbers that I think should be true. Given a prime $p$ and integers $α$ and $β$, can I show ...
0
votes
1answer
30 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$?
6
votes
1answer
43 views

Sum of the reciprocal of the prime-position primes.

The primes are $2, 3, 5, 7, 11, 13...$ The sum of the reciprocals of the primes diverges, proven by Euler: $$\sum_{n=1}^\infty{\frac{1}{p_n}}=\infty$$ Here, $p_n$ is the $n$-th prime. I'm asked to ...
-1
votes
0answers
20 views

Proof their are infinitely many primes of the for 6n+5 [duplicate]

how would i go about proving that there are infinitely many primes of the form $$6n+5$$ any help would be appreciated.
1
vote
0answers
33 views

Compositeness test for Wagstaff numbers

Is this proof acceptable ? Definition Let $W_p=\frac{2^p+1}{3} $ with $p$ prime and $p>3$ . Theorem If $W_p$ is prime then $7^{\frac{W_p-1}{2}} \equiv -1 \pmod {W_p}$ Proof Let $W_p$ be a ...