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
145 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.
1
vote
2answers
247 views

Is it sufficient for a number to be a prime if it is not divisible by prime numbers smaller than it?

I am student of computer science with no knowledge of maths. To write a small algorithm I searched for the solution first. There are many but almost all of them state that continue dividing the number ...
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.
3
votes
1answer
265 views

Is my conjecture true? : Every primorial is a superior highly regular number, and every superior highly regular number is a primorial.

I have invented two sets of positive integers: highly regular numbers and superior highly regular numbers. A positive integer $m \leq n$ is a regular of the positive integer $n$ if all prime numbers ...
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 ...
10
votes
5answers
1k views

Decimal form of irrational numbers

In the decimal form of an irrational number like: $$\pi=3.141592653589\ldots$$ Do we have all the numbers from $0$ to $9$. I verified $\pi$ and all the numbers are there. Is this true in general for ...
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
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 ...
14
votes
1answer
1k views

Finding smallest and largest prime factor of $\frac{200!}{180!}$

I originally started off by listing all the primes: $p<200$ then trying to calculate the prime factorisation of each (which I realise is a silly thing to do) I believe there must be a simpler way ...
1
vote
1answer
95 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)}) < ...
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 ...
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 ...
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 ...
2
votes
1answer
409 views

How do we prove $p_n\sim n\log(n\log(n))$ from the Prime Number Theorem?

Let $p_n$ be the $n$th prime. Could someone please help me with the steps between $\pi(n)\sim\dfrac{n}{\log(n)}$ and $n=\pi(p_n)$, to the statement $p_n\sim n\log(n\log(n))$?
4
votes
1answer
173 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 ...
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}$$
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 ...
2
votes
2answers
187 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 ...
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.
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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
0
votes
4answers
752 views

What is the largest prime number? [duplicate]

I want to know, what is the largest prime number? I know prime numbers are whole numbers that cannot be divided by any whole number except 1 and themselves, I also know some primes like 2, 3, 5, 7, ...
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 ...
6
votes
4answers
248 views

Tell whether $\dfrac{10^{91}-1}{9}$ is prime or not?

I really have no idea how to start. The only theorem considering prime numbers I know of is Fermat's little theorem and maybe its related with binomial theorem. Any help will be appreciated.
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?
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
119 views

Proving $\prod_{i=1}^np_i+1$ is not a perfect square

Let $m=\displaystyle{\prod_{i=1}^np_n}$ be the product of the first $n$ primes $(n>1)$. prove that $m+1$ cannot be a perfect square. I think that the opposite it correct: $m+1$ is not a ...
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
640 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 ...
4
votes
1answer
71 views

Primes in an Infinite Set

Let $S$ be the infinite set of positive integers whose members can be written with no digits except $0$ and $1$ and with no more than $1988$ $1s$. Show that some integer $n$ does not divide any member ...
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 ...
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 ...
0
votes
3answers
61 views

Find values of $n$ that yield a prime number

Let $n$ be a positive integer, and $\frac{n(n+1)}{2}-1$ is a prime number. Find all possible values of n. What I have so far is this: $$\frac{n(n+1)}{2}-1=2, n=2$$ Also, $n^2+n-2\over2$ can be ...
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 ...
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 ...
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 ...
2
votes
1answer
151 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 ...