Prime numbers are natural numbers 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

7
votes
1answer
170 views

Prove $18080108080 \sum_{k=0}^{1560-1} 10^{10k}+1$ is prime

I saw this fact on twitter: I would like to know how one would show this number is prime. Is there an elementary way to show that this number is prime? Is there a simplified primality testing ...
0
votes
0answers
45 views

Fast check of safe primes or Sophie Germain primes

If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$. In ...
2
votes
1answer
44 views

For an integer $n \geq 2$, let $m$ be the largest positive integer less than $n$ such that $m \mid n$. [closed]

Consider an integer $n \geq 2$, and $m$ the largest positive integer less than $n$ such that $m \mid n$. Then $n = mk$ for some positive integer $k$. Prove that $k$ is a prime number.
0
votes
1answer
38 views

Existence of at least one prime for all sequences in the family of sequences

Prove or disprove that for a fixed $n \in N$, there exists at least one prime among the integers of the form $2^{k}n+2^k-1$ for an arbitrary $k \in N$.
1
vote
0answers
47 views

Prime bounds under RH

Continuing from here, since $$ \sum_{k=1}^{\lfloor\log(n)\rfloor}\dfrac{\pi(n^{1/k})}{k}=\operatorname{li}(n)-\sum_{k=1}^{\infty}2\ ...
1
vote
2answers
223 views

Visualization of Eratosthenes’ sieve

In otherwise great paper on prime numbers, I found following visualization of Eratosthenes’ sieve: I found it somewhat scary and confusing. Is there any better visualization of Eratosthenes’ sieve ...
0
votes
4answers
112 views

Is at least one of $6k + 1$ or $6k-1$ prime?

We know that any prime number ( $> 2,3$) can be written in the form $6k+1$ or $6k-1$. Is it necessary that at least one of $6k+1$ or $6k-1$ is a prime number ?
0
votes
2answers
130 views

$9n^2-4$ only generates one prime? Why?

Instead of doing the work I was supposed to be doing, I played around with some numbers, and I noticed that for $n\in\mathbb{N}$, $9n^2-4$ only seems to generate a prime for $n=1$. Can anyone ...
0
votes
1answer
46 views

Q: Understanding Answer of 2012 AMC 8 - #18

The problem is: "What is the smallest positive integer that is neither prime nor square and that has no prime factor less than 50?". The solution for this problem goes like this: "Since the integer ...
1
vote
2answers
31 views

Prove that 1 is the only “common” divisor of the integers n and n+2

Let n be any odd integer. Prove that 1 is the only "common" divisor of the integers n and n+2. I think you have to find gcd(n, n+2) and say that since n odd then then n+2 will also be odd. Thus n + ...
9
votes
2answers
121 views

Sets of Prime Numbers Generated By an Irreducible Monic Polynomial

Given a non-constant integral irreducible monic polynomial $f(x)$, the prime factors of its value at integers $x\in\mathbb{N}$ forms a set $\mathcal{P}(f)$. Is it possible that ...
2
votes
1answer
83 views

Prime number upper bound

I am reading some written notes about a proof I do not understand, maybe some informations are missing. The result that has to be proved is the following: if $p_n$ is the $n$-th prime number, ...
1
vote
0answers
84 views

How I could transform this into product over primes :$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+…\frac{1}{2^p-1}$?

1)Can I transforme this sum into product OVER primes:$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+....\frac{1}{2^p-1}$ ? Note : p is prime number and ${2^p-1}$ is prime 2)I would be interest to know ...
5
votes
12answers
961 views

What are the properties of a prime number?

For instance, we know that odd numbers behave like: $$x = 2y + 1 \quad\text{where}\quad x,y\in\mathbb Z$$ For even numbers: $$a = 2b \quad\text{where}\quad a,b\in\mathbb Z$$ But what about prime ...
0
votes
1answer
194 views

Why elements of the set can be Goldbach pairs for a given even number?

Let's take even number $100$ as an example (an example in the paper): Fom $2$ to $\sqrt{100}$ there's four primes:$\ 2,\ 3,\ 5,\ 7.\ $Let $$ \begin{align*} &A=\{n: n \in \mathbb{Z^+}, ...
0
votes
1answer
27 views

Largest $k$ such that $(p-k) = \lceil \sqrt{(p-2k) p} \rceil$

Assume $p \in \mathbb P.$ Assume $0<p-2k<p$ and the next square larger than $p(p-2k)$ is $(p-k)^2$. It is trivial to show that $p(p-2k)+k^2$ is a square. Simply $p(p-2k)+k^2 = (p-k)^2.$ ...
3
votes
1answer
79 views

Prime number question

Can somebody please give me a hint on how to start this question: Let $a$ and $n$ be two positive integers with $a,n ≥ 2$. Assume that $a^n−1$ is a prime number. Prove that $a = 2$ and $n$ is a prime ...
3
votes
2answers
101 views

Given $N$, what is the next prime $p$?

Certain data structures in programming related to collections operate in an optimal way if they have prime number of elements. This means if a program (programmer) requires $N$ (any natural number) ...
3
votes
1answer
157 views

What is the 5000th happy prime number?

Im writing a program that finds the Nth happy prime number. I think it works, but to double check I want to compare what it returns for the 5000th happy prime number. The problem is, I dont know where ...
1
vote
2answers
40 views

The $i^{th}$ prime in a given ring R

When I say that $p_1=2$, I mean that the first prime in the standard ring of integers $(\mathbb{Z},*,+)$ is $2$. I was wondering whether the notion of ordering the primes like this can be generalized ...
5
votes
2answers
121 views

Is this Goldbach-type problem easy to solve?

Problem: Given an odd prime number $p$, are there odd prime numbers $q$, $p'$, $q'$ such that $\{p,q\} \neq \{ p',q'\}$ and $p+q = p'+q'$ ? This comment informs that it's an obvious ...
2
votes
2answers
573 views

Bijection between Prime numbers and Natural numbers

We know that if set $S$ is countable then this set and set of all natural numbers are equivalent, which means that there must be some bijection between this two sets $F:S\rightarrow N$. We know that ...
4
votes
1answer
205 views

Is $2013^{2014}+2014^{2015}+2015^{2013}+1$ a prime? (usage of a computer not allowed)

Prove or disprove: $$2013^{2014}+2014^{2015}+2015^{2013}+1$$ is a prime number, without using a computer. I tried to transform the expression $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, but couldn't reach ...
2
votes
0answers
158 views

Interchanging limits with the prime counting function

How does one justify that $$\lim_{s \to 1} \lim_{x \to \infty} \frac{\pi(x)}{x^s} = \lim_{x \to \infty} \lim_{s \to 1} \frac{\pi(x)}{x^s}, \quad s > 1,$$ without using the fact that the primes have ...
1
vote
1answer
44 views

Extending $f(p^k)$ where $p$ is prime

If we have a function $f(x)$, for which we know that $f(p^k)=(p^s+1)^k p^{sk}$ where $p$ is prime, $k$ is a real number, and $s$ is a constant, how do we find $f(x)$? My try: let $k=\log_p(x)$, so ...
0
votes
1answer
76 views

Given a prime p and an integer N, find the number of integers n such that 1≤n≤N and order(n!) is divisible by p

We are given a prime number $\leq 10^{18}$ and an integer N $(\leq N\leq 10^{18})$ how to find the number of integers lying in the range $1\leq n\leq N$ for which the order(n!) is a multiple of p? ...
0
votes
2answers
44 views

What is the mean prime power?

I found this definition in a book and I did not understand the meaning of it There exists a field of order q if and only if q is a prime power (i.e., $q = p^r$]) with p prime and r ∈ N. Moreover, if q ...
1
vote
1answer
71 views

Sum of reciprocals of primes for known primes.

I was reading through some old analytic number theory notes earlier and found the interesting fact that even though $\sum\frac{1}{p}$ diverges: $\sum_{\text{known primes}}\frac{1}{p} < 4$. ...
10
votes
4answers
1k views

Prime Partition

A prime partition of a number is a set of primes that sum to the number. For instance, {2 3 7} is a prime partition of $12$ because $2 + 3 + 7 = 12$. In fact, there ...
1
vote
2answers
70 views

Power of primes

We have proved that if $a > 3$, then $a$, $a+ 2$, and $a+ 4$ cannot be all primes in previous question. Can we say that they all be powers of primes?
3
votes
2answers
85 views

Extending primes

This question is more of a curiosity than anything. Start with a prime number and consider concatenating digits onto the right hand side. Sometimes you can make a prime and continue the process ...
1
vote
2answers
125 views

Prime factorization, distinct primes

Let $n=p^eq^f$ where $p$ and $q$ are distinct primes and $e$ and $f$ are positive integers. Show that $n$ has $(e + 1)(f + 1)$ distinct factors in $N$, and that the sum of all these factors is ...
1
vote
1answer
301 views

Sum of three primes equal to a prime [closed]

Does anyone know how to always get a prime from the sum of three primes? For example: 5+7+11=23, 17+29+43=89, etc.
4
votes
3answers
145 views

prime numbers and some conjectures

Consider triples $(p,q,r)$ of prime numbers $p$, $q$ and $r$ such that $(p+1)(q+1)=(r+1)$. Here are some examples : $(2,3,11), (3,7,31)$. How to prove there are infinitely many such triples?! I ...
2
votes
1answer
81 views

Primes Number Theory

For which primes $p$ is $2^p+1$ divisible by $p$? What I have been doing is: $2^p+1\equiv 0\pmod p$ $2^p\equiv -1\pmod p$ Then by Fermat's Theorem, we get $2^p\equiv 2\pmod p$ This shows ...
4
votes
1answer
146 views

A problem in prime number theory

I was wondering if anybody here might provide me with a hint for this rather innocuous-looking problem: If $X:= \{pq: p, q \mbox{ are prime numbers and } p\neq q\}.$ In addition, let us suppose that ...
2
votes
2answers
110 views

Prime numbers like 113

The number 113 is prime. The sum, product and all permutations of it's digits are prime. Are there any other such prime numbers?
3
votes
2answers
118 views

$n^2-79n+1601$ always a prime?

I am struggling with proving or disproving this: $n^2-79n+1601$ is a prime for all natural numbers $n$ (except multiples of $1601$). This somehow has a relation to Stanislaw Ulam spiral. What ...
3
votes
0answers
59 views

How does Hildebrands proof of the prime number theorem via large sieve work?

How does the sieve inequality (I may not know the most general form) lead to the distribution of primes? To me, these concepts do not seem to be related. Can their connection be described in a ...
2
votes
2answers
157 views

How to prove that this Proth number cannot be a prime number? (without using a computer)

Without using a computer prove that this Proth number cannot be a prime number : $$43373\cdot 2^{49822}+1$$
4
votes
1answer
57 views

Congruences with prime number and factorial

Prove that if $p\equiv 1 \pmod{4}$ is a prime number and $$x\equiv \pm \left(\frac{p-1}{2}\right)! \pmod{p}$$ then $x^2\equiv -1 \pmod{p}$ I think Wilson's theorem will come in handy here, used ...
2
votes
2answers
73 views

Does factorization end with a prime number?

When doing factorization, I have always taught kids to work from the outside in. So for the number $28$, you start with $1$ and $28$, then $2$ and $14$, then $4$ and $7$. And once you reach the ...
11
votes
3answers
250 views

Prove or disprove: $99^{100}+100^{101}+101^{99}+1$ is a prime number

Prove or disprove: $$99^{100}+100^{101}+101^{99}+1$$ is a prime number. My idea: let $100^{101}=x^{x+1}$,then $$99^{100}+100^{101}+101^{99}+1=(x-1)^{x}+x^{x+1}+(x+1)^{x-1}+1$$ is prime number? I ...
20
votes
2answers
316 views

Related to greatest prime number that divides $n.$

I don't even have an idea of how to start working on this one: Let $p(n)$ denote the greatest prime number that divides $n.$ Show that there exists infinitely many positive integers $m$ such that ...
1
vote
1answer
98 views

How to prove a number is not a prime number (without a computer)

Show that $$5994937829$$ is not prime number How can I use math methods to prove it, and I know that this be proven using computer. But I can use only math methods to solve it.
1
vote
1answer
43 views

What's the best software for primality tests of huge numbers? (check if an integer is prime or not)

I just read an article about huge prime numbers (some with more than 10millions digits!) that are discovered using software that check if an integer is prime or not (primality test sofwares). What is ...
4
votes
2answers
48 views

Density in $\mathbb{R}_{ +}$ of a subgroup of $\mathbb{Q}_{> 0}$?

Let $\phi : \mathbb{Q}_{>0} \to \mathbb{Z}$ be the group morphism defined by $\phi(p) = p$ for $p$ a prime number. It follows that $\phi(1)=0$, $\phi(a.b) = \phi(a)+\phi(b)$, $\phi(a^{-1}) = ...
10
votes
2answers
1k views

Do 4 consecutive primes always form a polygon?

Related to this question, if 4 segments have length of 4 consecutive primes, can they always form a 4-vertex polygon? This question occurred to me out of sheer curiosity, but now I can't prove or ...
1
vote
1answer
64 views

Is there a prime between $k$ and $\dfrac{11}{9}k$, $\forall k\ge 24$?

Given $k\in\mathbb{N}$, $k\ge 24$, is there always a prime number in the interval $\left[k,\dfrac{11}{9}k\right]$? I tried to verify this statement with the computer and it seems to hold. Is it ...
3
votes
1answer
155 views

An integral and $\pi(n)$

Are there polynomials $P,Q\in \mathbb{R}[x]$ satisfying : $$\int_{0}^{\log n}\frac{P(x)}{Q(x)}\,\mathrm{d}x=\frac{n}{\pi(n)}\quad \text{ for infinitely many }n\in \mathbb{N}$$ Here $\pi(n)$ is the ...