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

2
votes
1answer
64 views

Prove that there are an infinity of prime $ak+b$, $a$ and $b$ coprimes

We have to integers $a,b$. I need to show that if $a$ and $b$ are coprimes then the set of prime numbers of kind $ak+b$ is infinite. How could I show it ? I know how to do that for $4k+3$ or $4k+1$, ...
2
votes
3answers
1k views

Smallest Prime Factor - Why does this algorithm find prime numbers?

I have been looking at the problems on Project Euler and a number of them have required me to be able to find the prime factorisation of a given number. While looking for quick ways to do this, I ...
2
votes
1answer
142 views

Algorithm for checking Prime Power

Suppose we are given some arbitrary positive integer. How can we check whether the integer is a prime power? Brute force would be very inefficient in this case.
2
votes
2answers
64 views

Does there exist any integer $ n> 1$ for which $6^{2n}-25$ is prime?

I got this question on a test and I am really curious hoe you would approach it. I tried to prove stuff using the congruence laws but I didn't manage to prove anything.
2
votes
7answers
140 views

Finding an integer (if one exists) $n$ such that $n$, $n+1$, $n+2$, $n+3$, $n+4$ are all composite

I started off by thinking I would have to work $\bmod 24$ (as $24=1\cdot2\cdot3\cdot4$) But I then decided to multiply all of the terms together, and have ended up with a rather large expression. I'm ...
2
votes
1answer
92 views

Show that $\mathbb{Q}(\zeta)$ contains one of the two numbers $\sqrt{\pm5}$ and decide which one is contained in $\mathbb{Q}(\zeta)$.

Let $\zeta$ be the 15th primitive root of unity in $\mathbb{C}$, show that $\mathbb{Q}(\zeta)$ contains one of the two numbers $\sqrt{\pm5}$ and decide which one is contained in $\mathbb{Q}(\zeta)$. ...
1
vote
1answer
40 views

Is my proof correct regarding the non primality of $2\cdot 17^a +1$?

Today I need your help to know if the proof I have provided below is correct or not. I want to prove that there is no prime of the form $2\cdot 17^a+1$ where $a\in \mathbb N$. Now, first of all, I ...
0
votes
1answer
76 views

How to prove if an arithmetic function is multiplicative?

I know that for an arithmetic function to be multiplicative then $f(nm)=f(n)f(m)$ for $(n,m)=1$ I have just proved that: $$f(n) = \left\{ \begin{array}{l l} 0 & \quad \text{if 10|n}\\ ...
3
votes
1answer
75 views

Existence of semi-primitive primes modulo a special class of numbers

Let $p$ be a prime and $N$ be an integer. Then $p$ is called semi-primitive modulo $N$ if there exists a positive integer $j$ such that $p^j \equiv -1 \pmod{N}$. Now let $m$ be a positive integer ...
2
votes
0answers
59 views

$n$th prime bounded from above?

Let $p_n$ be the $n$th prime, $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial), and $\sigma(n)=\sum_{d|n}^{}d$ (divisor function). Does $\text{exp}\bigg(\dfrac{\pi^2}{6 ...
3
votes
1answer
93 views

Existence of a prime partition

I'm interested in finding out whether there exists a prime partition of a given positive integer $N>1$ such that the partition has specific number of parts. For instance, as given in another ...
3
votes
2answers
60 views

$\pi(x)\leq \frac x{f(x)}$ for some unbounded function $f(x)$

Let $\pi(x)$ denote the number of primes $\le x$. Can one prove $$\pi(x)\leq \frac x{f(x)}$$ for some function $f(x)(x\gt0)$, and $f(x)$ is unbounded? Please do not refer to prime number ...
2
votes
2answers
291 views

Complexity of finding the largest prime factor of a composite number

Is finding the largest prime factor of a number computationally easier than factoring the number into powers of primes?
1
vote
1answer
94 views

Using Bertrand's Postulate

Using Bertrand's postulate which states: For every integer $n \geq 1$ there is a prime number p such that $n<p\leq 2n$ Prove that there exists infinitely many primes whose decimal expansion ...
5
votes
1answer
55 views

Show $x^{\pi(x)} < 3^x$ using the PNT.

Using the Prime Number Theorem show that: $$x^{\pi(x)} < 3^x$$ for sufficiently large $x$. I started off by taking the $\log$ of the inequality such that: $$\log(x^{\pi(x)}) < ...
4
votes
1answer
172 views

Proof of Infinite Primes in the form $10^{\lceil k \log_{10}(n) \rceil }+n^{k-1}$

Let $k$ be any positive integer then how to prove that the sequence $$Q_k=10^{\lceil k \log_{10}(n) \rceil }+n^{k-1}$$ Contains infinitely many primes? It seems like because if you look at some ...
5
votes
1answer
344 views

Prove that there exists an $m$ such that for any $n>m$ there exists at least one prime between $c_n$ and $n$

Let $c_n$ be the $n$-th composite. Then the problem is to prove that- $\pi(c_n)-\pi(n)>0$ $\forall n>m$ I have tried to progress in the problem using an elementary approach. So far I have ...
4
votes
2answers
148 views

$n$th prime & prime number theorem

Let $p_n$ be the $n$th prime. If $\pi(n)\sim \dfrac{n}{\log (n)}$ then $p_n\sim n\log n$ (Hardy 1938). A closer approximation is $\pi(n)\sim\text{Li}(n)$. Is there a similarly improved definition for ...
9
votes
3answers
236 views

Does $\sum_{p\in\mathbb P}\frac {( - 1)^{[\sqrt p\,]}}{p}$ converges?

Does $$\sum_{p\in\mathbb P}\frac {( - 1)^{[\sqrt p\,]}}{p}$$ converges ? I know that the following $\sum_{p\in\mathbb P} \frac{1}{p}$ diverges, we can find proofs on Wikepedia Divergence of the ...
2
votes
2answers
186 views

Asymptotic divisor function / primorials

Let $p_n\#\equiv\prod_{k=1}^{n}p_k$ (primorial), and $\sigma(n)=\sum_{d|n}^{}d$ (divisor function). Could someone please tell me what the general asymptotic of $\dfrac{\sigma(p_n\#)}{p_n\#}$ is? It ...
2
votes
5answers
72 views

Understandng euclids theorem

Reading this Wikipedia article, it states "If q is not prime, then some prime factor p divides q" Why does some prime factor divide q? Does mean that for any number there is some prime factor p that ...
4
votes
1answer
90 views

Sum of Residues Modulo $p^2$.

Let $p$ be an odd prime. Prove that $$ \sum_{k = 1}^{p-1} k^{2p-1} \equiv \frac{p(p+1)}2 \pmod{p^2}$$
1
vote
1answer
39 views

Finding the Best Constant in Prime Counting Function Relation

How close can we approximate the best constant $c$ such that $n^{\pi(2n)- \pi(n)} \le c^n$ for all positive integers $n$. I know that $c = 4$ works from $n^{\pi(2n)-\pi(n)} < \prod_{n < p \le ...
0
votes
3answers
77 views

Find primes $p_1,p_2,..,p_6$ such that $1+\prod_{i=1}^{6}p_i $is not prime

Show that if$$ p_1, p_2, p_3, p_4, p_5, p_6 $$are primes, then $$1+\prod_{i=1}^{6}p_i$$ is not necessarily prime by using a specic example.
1
vote
0answers
44 views

Existence of primes $p$ such that all the prime divisors of $p+1$ divide $p-1$

This question recently came up to me in a project and is not taken from a textbook. I would like to know if any characterization of such primes is known from literature. They are seemingly rare but do ...
1
vote
1answer
156 views

Does this mean some Wall-Sun-Sun primes have already been found?

In the PrimeGrid project statistics page for Wall-Sun-Sun Prime Search, it says, Wall-Sun-Suns ... 2 Near Wall-Sun-Suns ... 208 However, all the internet search ...
3
votes
0answers
63 views

When is $f(n)=\sum\limits_{d\mid n}\sigma(d)$ prime?

When is $f(n)=\sum\limits_{d\mid n}\sigma(d)$ prime? Note, $f$ is multiplicative and $\sigma(n)>1, \;n>1$. Therefore $f(n)$ is prime only when $n=p^\alpha$, with $p$ prime, $\alpha\geq1$. ...
86
votes
3answers
3k 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 ...
1
vote
0answers
50 views

Are there such prime giving functions?

Here let us define a function $f : \mathbb{N} \rightarrow \mathbb{N}$ , such that for every $n$ , The sequence $\{f(n) ,f(n)+1 ,f(n)+2 , f(n)+3, \dots , f(n)+n\}$ contains atleast $1$ prime . Let us ...
3
votes
0answers
172 views

Conjecture on OEIS A167055

OEIS A167055 Numbers n such that $12n + 5$ is prime. $0, 1, 2, 3, 4, 7, 8, 9, 11, 12, 14, 16, 19, 21,...$ are items of OEIS A167055. I conjecture that the set of the sum of every two items of this ...
1
vote
0answers
103 views

Prime Zeta Function

Does $$\sum_{p \text{ prime}} \frac{1}{p^s} \sim \log \zeta(s) \quad \text{as} \quad s \to 1^+$$ imply $$\sum_{p \leq n} \frac{1}{p} \sim \log H_n \quad \text{as} \quad n \to \infty,$$ where $H_n$ is ...
3
votes
1answer
279 views

A Shorter Proof of Rosser's Theorem Without Using The Prime Number Theorem

While researching on the elementary proof of Bertrand's Postulate I came to know about a theorem of Rosser's which states that $p_n$ $>$ $n$ $\text{ln}$ $n$. I have seen Rosser's original proof and ...
4
votes
1answer
115 views

Is this sequence monotonically decreasing?

Let $a_n = \frac{p_n - p_{n-1}}{p_n \log p_n}$ where $p_n$ denotes the $n$-th prime. Is this sequence decreasing (or decreasing after some $N$)?
1
vote
2answers
194 views

About twin primes and their happy mothers.

Let's say that a positive integer $n$ is a happy mother if $6$ divides $n$ and $(n-1,n+1)$ is a pair of twin primes. Is the difference between two consecutive happy mothers necessarily a happy mother ...
1
vote
0answers
84 views

About a paper by Gold & Tucker (characterizing twin primes)

I've carefully looked at the questions on prime and twin prime, but the following question seems not to habe been asked before. Context: In the paper by Jeffrey F. Gold and Don H. Tucker titled A ...
1
vote
3answers
37 views

Why is $a^c-1$ composite if $a>2$ or if $c$ is composite?

Here is the original theorem from my book (A Course in Number Theory by H.E.Rose, 2nd edition): Let $a>1$ and $c>1$ be integers. The integer $a^c-1$ is composite if $a>2$ or if $c$ is ...
4
votes
2answers
127 views

Do prime numbers satisfy this?

Is this true that $n\log\left(\frac{p_n}{p_{n+1}}\right)$ is bounded, where $p_n$ is the $n$-th prime number?
2
votes
0answers
42 views

Does sum over primes of $p^{-z}$ diverge for all Re(z) = 1?

Let the function q(z) of one complex variable z be the sum over all primes p of (1/p^z). I was wondering about the complex zeros of q(z) [hoping that this problem might be much easier than the same ...
0
votes
1answer
88 views

Show that $b_n > b_{n-1}$ where $\frac{a_n}{b_n}$ are the n:th harmonic number

Let $H_n=\frac{a_n}{b_n}$ where $H_n$ is a n:th harmonic number and $a_n$ and $b_n$ are coprimes. 1/ If $n$ is a prime power, show that $b_n > b_{n-1}$ 2/ Find the integer factorization of ...
4
votes
5answers
637 views

Is $n^2 + n + 1$ prime for all n?

I recently stumbled across this question in a test. Paul says that "$n^2+n+1$ is prime $\forall\:n\in \mathbb{N}$". Paul is correct, because... Paul is wrong, because... The ...
9
votes
2answers
2k views

Doubt in finding number of non-prime factors of an integer

The question is: Find the number of non-prime factors of $4^{10} \times 7^3 \times 5^9$. I represented the number as $2^{20} \times 7^3 \times 5^9$ then the number of factors of this integer ...
1
vote
2answers
55 views

Integer-valued polynomial

Let $f(x) \in \mathbb{Q}[x]$, and suppose $f(n)$ is an integer for all large integer $n$. Prove that $f(n)$ is an integer for small positive integers $n$. I read the answer from here is the hilbert ...
3
votes
2answers
57 views

Assume that $p$ is a prime, $a$ and $b$ are integers such that $p \mid b$ and $am+b=1$.

Assume that $p$ is a prime, $a$ and $b$ are integers such that $p \mid b$ and $am+b=1$. Prove that $x \equiv m(1+b+b^2+...+b^{k-1} \bmod {p^k}$ is the solution to $ax\equiv 1 \bmod{p^k}$. So I got ...
2
votes
1answer
76 views

Prove that there are infinitely many relatively prime solutions of $x^2+y^2=z^3$

Show that for all integers k, there is a solution with $x=3k^2-1$ and $z=k^2+1$ You will need to calculate $y$ to show that there is such a solution, and show that the solution $(x,y,z)$ is ...
0
votes
1answer
35 views

Lemma about a prime ideal in a commutative ring with identity

I am trying to prove the Cyclotomic polynomial is irreducible over $\mathbb{Q}[x]$ for any prime $p$ using Eisenstein's Criterion. However, I would like to be more specific and prove the following ...
1
vote
0answers
55 views

Estimating the Twin prime constant

http://numbers.computation.free.fr/Constants/Primes/twin.html it says: "This last constant occurs in some asymptotic estimations involving primes and it's interesting to observe that it may be ...
2
votes
1answer
149 views

Find all ordered triples $(x,y,z)$ of prime numbers satisfying equation $x(x+y)=z+120$

This question was from my Math Challenge II Number Theory packet, and I don't get how to do it. I know you can distribute to get $x^2+xy=z+120$, and $x^2+xy-z=120$, but that's as far as I got. Can ...
2
votes
1answer
112 views

Minimum Argument Difference to Make the Lower Bound > the Upper Bound

Assume $g$ is a function that grows asymptotically as $$ g(n) \in\frac n {log(n)} + O(\sqrt n),\,n \in \Bbb N\tag1 $$ I wish to find $h(n)$ such that $$ g(n) \le g(n+h(n)). $$ i.e. Given the bounds ...
0
votes
3answers
168 views

Pi and the sum of reciprocals of primes?

So I know that $$\sum_{\underset{\Large p\; prime}{p=1}}^{\infty}\frac{1}{p}$$ blows up. But doing some fun on mathematica I found out that when the sum isn't infinite, it was so close to $3$ and I ...
0
votes
2answers
46 views

solving this equation using prime numbers

Solve in $\mathbb{Z}$ the following equation: $3^x$+$3^y$=$738$, using prime numbers concept and decomposition in prime factors... I noticed that the above equation is symmetrical to $x$ and $y$, ...