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
0answers
31 views

Infinitely many primes of the form $16n+1$? [duplicate]

As the title states I need to prove there are infinitely primes of the form $16n+1$ but I have absolutely no idea how to do it.
0
votes
0answers
51 views

Are all the numbers in this sequence a prime number?Sequence : $31 , 331, 3331, 33331$ [duplicate]

The given sequence is : $31,331,3331,33331....$ where the $n^{th}$ number has n $3$'s followed by a $1$. The question asked is to find are all the numbers prime? If not all how many terms from start ...
1
vote
0answers
16 views

Find all functions such that $f(m)+f(n)|m^p+n^p$

For fixed prime number $p$, find all $f:\mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ such that $f(m)+f(n)\mid m^p+n^p$ for all $m,n\in \mathbb{Z}^+$ I managed to get only that for prime $q$ we have ...
2
votes
1answer
90 views

Conjecture on sum of powers

Let $n$ be an odd number, $x,y$ integers and $p$ a prime number. Now, suppose that $p\ne n$ and $$ p|\frac{x^n+y^n}{x+y} $$ Then, I have been observed that $p \equiv 1 \pmod{n}$. This is, all of the ...
2
votes
1answer
23 views

Why are primes of the form p^2 - 2 for prime p seemingly unusually likely to be factors of prime-exponent Mersenne numbers?

The sequence A049002 (primes of form $q^2 - 2$, where $q$ is prime) appears to contain a high proportion of elements that are factors of prime-exponent Mersenne numbers (see below). I wonder why? ...
1
vote
2answers
51 views

Proving the set of prime numbers in $\mathbb{Z+}$ is infinite

I'm trying to prove that for any $N \in \mathbb{Z^+}$, there exists only finite many integers $n$ with $\varphi(n) = N$ (i.e. finite amount of numbers that have $N$ numbers relatively prime to them) ...
0
votes
1answer
13 views

Modular Exponentiation doesn't work on a prime mod?

For 83627264^275372 mod 277 using modular exponentiation, I noticed that things weren't lining up when I checked them on Wolfram. So far I have this: 83627264^1 mod 277 = 133 83627264^2 mod 277 = 238 ...
0
votes
3answers
43 views

How many numbers less than 100 have the sum of factors as odd?

How many numbers less than 100 have the sum of factors as odd? Answer is 16 This question and explanation is taken from careerbless.com The link given derives the answer using some ...
40
votes
5answers
973 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem is as follows: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$ cannot be a prime. I came across this problem accidentally ...
2
votes
0answers
35 views

Lehmann primality test

How to calculate final probability that a given number is prime after 1000 iterations, when using Lehmann primality test ?
1
vote
1answer
59 views

There are infinitely many primes congruent to 9 mod 10

I want to show that there are infinitely many primes $p$ such that $p = 9 \pmod {10}$. First, I can see that 19 is one of them. Assume there are finitely many, i.e., 19, $p_1, p_2 , \cdots , p_k$. ...
-1
votes
0answers
43 views

If $p$ is congruent to 3 mod 4 then $2^p -1$ is not a prime

Let $p=3 \pmod 4$ be a prime number such that $q = 2p+1$ is also a prime number. Then I want to show that $q$ divides $2^p -1$. Thank you so much. Any help will be appreciated.
2
votes
0answers
33 views

Is there anyway to find how many prime factors has a composite number without knowing them?

Let's call f(n) the function that gives us the number of different prime factors of a composite number n For example: f(24)=2 Let's call g(n) the function that gives us the number of prime factors of ...
3
votes
1answer
73 views

Fix $k∈\Bbb{N}$. An integer $n$ is said to be $k$-th power free if there exists no prime $p$ such that $p^k | n$…

Fix $k∈\Bbb{N}$. An integer $n$ is said to be $k$-th power free if there exists no prime $p$ such that $p^k | n$. Prove that for any $m∈\Bbb{N} $ greater that 1, there exists $m$ consecutive integers ...
5
votes
4answers
66 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 = ...
3
votes
2answers
33 views

Proof of (n) and (n+1) Sharing No Prime Factors

A number $(n)$ has a set of prime factors $\{\alpha_1, \alpha_2,...\alpha_\epsilon\}$ and a number $(n+1)$ has a set of prime factors $\{\beta_1,\beta_2,...\beta_\psi\}$. The conjunction, ...
1
vote
0answers
32 views

Prove that $p=13$, given that $(p-1)/4$ and $(p+1)/2$ are prime. [duplicate]

Suppose $p$ is a prime such that $(p-1)/4$ and $(p+1)/2$ are also primes. Show that $p=13$. I thought about taking $p_1=(p-1)/4$ and $p_2=(p+1)/2$ and proving that there is only one possible case ...
0
votes
2answers
78 views

What is the possible relation between the twin prime conjecture and the Goldbach's conjecture

Just a curiosity: What is the possible relation between the twin prime conjecture and the Goldbach's conjecture stating that every even integer greater than $2$ can be expressed as the sum of two ...
1
vote
0answers
16 views

Lower bound on $\pi(x/2)$

I have seen the bound, $\pi(x/2)^2\gg\frac{x^2}{\log^2x}$ (In particular here http://staff.polito.it/danilo.bazzanella/PhD_files/Not%20always%20buried%20deep%20(Pollack).pdf page 212) Can someone ...
3
votes
2answers
85 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 ...
6
votes
2answers
58 views

How to prove $p^2 \mid \binom {2p} {p }-2$ for prime $p$?

How to prove $p^2 \mid \binom {2p} {p } -2$ for prime $p$? I have a hint: for $1 \le i \le p-1$, $p \mid \binom p i$. I cannot even start the proof. Please help.
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 ...
1
vote
1answer
65 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!$ ...
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 ...
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 ...
0
votes
1answer
41 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?$$
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 ...
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 ...
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
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 ...
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
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= ...
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
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 ...
1
vote
4answers
61 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
84 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
175 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
584 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
992 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
227 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 ...