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

1
vote
1answer
683 views

Set of numbers pairwise relatively prime

Given a positve integer n, we can find infinitely many positve integers $b$ such that the $n-1$ integers in the set $\{b+1,\,2b+1,\,3b+1,\,...,\,(n-1)b+1\}$ are pairwise relatively prime. I assume ...
1
vote
1answer
90 views

Proof of Generalized Primorial Primes

Let's call the numbers of the form $k\times p\# \mp1$, the Generalized Primorial Primes. One can find many $k$ for a fixed $p$ such that $k\times p\# \mp1$ be prime. As an example for $p = 8933$ ...
1
vote
0answers
101 views

intuitive meaning behind Mertens' theorem

I have just been introduced the topic of distribution of primes, big O notation and aymptotic functions so please correct me if I say something that does not make sense. I am looking to get an ...
9
votes
0answers
445 views

Why does this identity equal the number of primes?

Can someone explain why this identity gives the number of primes? I don't understand it. $D_{0,a}(n) = 1$ $D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} \binom{k}{j}\sum_{m=a+1}^{\lfloor ...
7
votes
5answers
2k views

prime divisor of $3n+2$ proof

I have to prove that any number of the form $3n+2$ has a prime factor of the form $3m+2$. Ive started the proof I tried saying by the division algorithm the prime factor is either the form ...
-1
votes
3answers
546 views

When a prime number p divides $ab$ then we have either p divides a or p divides b.Prove that $\sqrt {p} $ is not rational for any prime number p.

When a prime number $p$ divides $ ab $ then we have either $p$ divides $a$ or $p$ divides $b$. Prove that $ \sqrt p $ is not rational for any prime number $p$.
3
votes
2answers
161 views

A series with prime numbers and fractional parts

Considering $p_{n}$ the nth prime number, then compute the limit: $$\lim_{n\to\infty} \left\{ \dfrac{1}{p_{1}} + \frac{1}{p_{2}}+\cdots+\frac{1}{p_{n}} \right\} - \{\log{\log n } \}$$ where $\{ x ...
5
votes
1answer
164 views

What are primes in the form of $2^n+1$ called?

What are primes in the form of $2^n+1$ called? I know that those of form $2^n-1$ are Mersenne primes, but I'm not sure about the other ones.
1
vote
1answer
111 views

3 primes conjecture

let be $ p,q,r $ prime numbers AND 'n' an integer is then true that we can always look for p,q,r and an integer n so $$ p^{n}+q=r $$ $ 5+2=7$ $ 2^{3}+3=11 $ $ 3^{4}+2=83 $ abnd so on
0
votes
0answers
61 views

Are the Prime Numbers $O(f(n))$ where $f(n)$ is some polynomial?

Are the prime number, denoted $ p(n) $, $O(f(n))$, for any polynomial $f(n)$?
0
votes
1answer
313 views

If n is an odd pseudo prime number, then $M_n = 2^n-1$ is a larger one

I came across this Theorem in "Elementary Number theorem" by David B. Burton : "If n is an odd pseudo prime number, then $M_n = 2^n-1$ is a larger one." I am not able to understand why this result ...
6
votes
1answer
104 views

Testing for convergence $\sum_{j=1}^{\infty}\frac{1}{\sum_{i=1}^{j}p_i}$

How would we test for convergence the series below? $$\sum_{j=1}^{\infty}\frac{1}{\sum_{i=1}^{j}p_i}$$ where $p_i$ is the $i$th prime number. I'd be glad to learn an elementary way. Thanks.
3
votes
1answer
219 views

Is this the way to estimate the amount of lucky twins?

To estimate the amount of prime twins between $3$ and $x$ we just take $x \prod_{p}(1-2/p)$ where $p$ runs over the primes between $3$ and $\sqrt x$. Lucky numbers are similar to prime numbers. Does ...
0
votes
0answers
196 views

Iterate over combinations ordered by sum

I have a sorted list of a large number of primes. I want to iterate over combinations of fixed size $n$ in increasing order of their sum. Naturally the standard approach for $n=4$: $$s_0 = \sum(A, ...
1
vote
2answers
38 views

Is there a pattern (or a name and expression for the pattern) of the intervals between all primes?

With the recent interest in Mersenne primes, I got thinking whether there was any mathematical expression for the pattern of intervals (or sequence composed of interval lengths) between ordinary prime ...
7
votes
1answer
168 views

Apparent patterns in ratios of consecutive primes

I was plotting the values of $\frac{P(n+1)}{P(n)+2}$, where $P(n)$ is the nth prime number. I noticed very easily that the values seem to belong very nicely to a set of "trajectories". They clearly ...
1
vote
2answers
117 views

Problem over prime numbers

Which is the largest integer $n<1000$ so that $n$, $n+2$ and $n+4$ are primes? I have tried to solve this problem but have not reached an argument worth
4
votes
3answers
131 views

prove , if $p,q$ be two primes with the property , $q$=$p$+1 then $p$=2 and $q$=3

prove , if $p,q$ are two primes with the property , $q$=$p$+1 then $p$=2 and $q$=3 how can we prove something like that ? my information in number theory is not big , and i have no idea about the ...
2
votes
2answers
236 views

Finding a counterexample to a Prime Factorization Conjecture

Let $\mathbb{Z}_{\geq 2}$ be the set of natural numbers starting at 2: $$\mathbb{Z}_{\geq 2}= \{2, 3, 4, 5,\ldots\}.$$ An natural number's prime factorization is odd if the total number of primes in ...
3
votes
1answer
99 views

For which prime $p$ is $x^4 \equiv -1 \pmod{p}$ solvable?

Let $p$ be a prime. I know, due to Euler's criterion, that if $x^2 \equiv -1 \pmod{p}$ is solvable, then $p \equiv 1 \pmod{4}$ simply because I inspect which $p$ that are such that $(-1)^\frac{p-1}{2} ...
0
votes
1answer
115 views

Proving finite vs infinite representation of $p/q$ in base-$b$?

Reading up on positional notation and converting between different bases, I came across this statement: For integers p and q with gcd(p, q) = 1, the fraction p/q has a finite representation in base b ...
4
votes
1answer
150 views

What happened to the Mertens constant in the strong prime twins conjecture ??

To estimate the amount of primes in an interval $\left(2,x\right)$ one might naively sieve by computing $ x \left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)...\left(1-\dfrac{1}{p_i}\right)$ ...
2
votes
3answers
416 views

What can primes, except 2, 3, and 5, be congruent to $\pmod {30}$?

After some trials, I found out that a prime $p \gt 5$ is congruent to $q\pmod{30}$, where $q$ is also a prime, and $1 \le q \lt 30 \;$ (i.e. $p \equiv q\pmod{30}.$ Is there a way to write a formal ...
2
votes
1answer
72 views

What error bound would an epsilon closer to the Riemann hypothesis give?

$s=1$ line gives: $$\psi(x) = x(1+o(1))$$ classical zero free region gives: $$\psi(x) = x + O(x e^{-c \sqrt{\log x}})$$ for some positive constant $\delta$ RH gives: $$\psi(x) = x + ...
2
votes
1answer
129 views

Show that Fermat number $F_n$ and its index $n$ are coprime.

I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this? I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots ...
5
votes
1answer
144 views

Sequence involving primes of form $n^2 + n+1$

Looking at prime numbers $p_i $ of the form $n^2+n+1$ and the derived expression $$1 - \prod_{i=1}^{j}\frac{(p_i-1)}{p_i}$$ it seems (I do not claim it and do not see why it should be true) that ...
2
votes
1answer
318 views

How does sieve that Chen used to prove Chen's theorem work?

In the Number Theory for Computing, Song Y. Yan states that Chen used "complicated arguments based on sieve method", when proving what is now called Chen's theorem. How does this sieve work? Does it ...
3
votes
1answer
95 views

Question involving prime numbers, *brothers* numbers.

I thought about the following problem, probably it already appears in mathematical literature. Definition 1: Operator $\unrhd$, is binary operation, defined for natural numbers as follows: To every ...
3
votes
2answers
625 views

Prove that if $a$, $b$, and $n$ are positive integers such that $a^n|b^n$ then $a|b$

This is how I did it, but not sure if it is a correct proof. Assume that $a^n | b^n$. Then $(a^n, b^n) = a^n$. So, $$b^n = a^n(p_1p_2p_3...p_k)^n$$ $$b^n = (ap_1p_2p_3...p_k)^n$$ $$b = ...
1
vote
1answer
61 views

Are there infinitely many primes of the form $n^k+l_0$ for fixed $l_0$ when $(n,k)$ runs through the $\mathbb N\times ({{\mathbb N}\setminus\{1\}}$)?

I do not know if this what I am going to ask is immediate consequence of something known but if not it may have an easy answer which I do not see, so any help would be great. Let us define sequence ...
0
votes
1answer
1k views

Prove that if $n$ is a composite, then $2^n-1$ is composite. [duplicate]

Not sure if I'm doing this correctly but this is what I've done: Assume that $n$ is composite and suppose $2^n-1$ is a prime for $n \gt 2$. Then, $2^n-1 = 2k$ for some $k \in \Bbb Z $, $\forall n$. ...
1
vote
2answers
231 views

Indices - Numbers as a product of prime numbers

I've checked the internet which only provides basic $x^2 \times x^3 = x^5$ information and have concluded that I need resort to a Q & A website. The basics of indices are fine for me, but it's ...
3
votes
2answers
572 views

When is the number 11111…1 a prime number?

For which $n$ is the sum: $$\sum_{k=0}^{n}10^k$$ a prime number? Are they finite?
5
votes
1answer
226 views

Always a prime between $x$ and $x+cf(x)$

What is the asymptotically slowest growing function $f(x)$, such that there exists constants $a$ and $b$, such that for all $x>a$, there is always a prime between $x$ and $x+bf(x)$? $f(x)=x$ ...
2
votes
1answer
74 views

How many solutions to prime = $2 b^2 c^2 + 2 c^2 a^2 + 2 a^2 b^2 - a^4 - b^4 - c^4$

Let $a,b,c$ be integers, no sign restriction. Let $p$ be a given prime. How to find the number of solutions to $p = 2 b^2 c^2 + 2 c^2 a^2 + 2 a^2 b^2 - a^4 - b^4 - c^4$ ? Note, from Heron's ...
0
votes
1answer
35 views

What is the pair $(n,k)$ called where $n$ is an integer and $k$ is the ordered factorization index?

I’m developing a number class (as in Object-Oriented Programming) and am wondering what to call it. At its core, it represents an integer, but in a way in which not all integers are unique. What it ...
2
votes
1answer
120 views

Primes of form $n^{n+1} - (n+1)^n$

I was playing with some numbers today and saw (with a bit of joy) that $3^4 - 4^3$ is the $(3 + 4)$th prime number, which is sort of neat. Then naturally I asked the question, what kind of number $n$ ...
3
votes
3answers
174 views

How many solutions to prime = $a^3+b^3+c^3 - 3abc$

Let $a,b,c$ be integers. Let $p$ be a given prime. How to find the number of solutions to $p = a^3+b^3+c^3 - 3abc$ ? Another question is ; let $w$ be a positive integer. Let $f(w)$ be the number of ...
1
vote
2answers
93 views

How many solutions to prime = $(d^2-2ad+b^2-2ab+2a^2)(d^2-2cd+2c^2-2bc+b^2)$?

Let $a,b,c,d$ be integers $>-1$. Let $p$ be a given prime. How to find the number of solutions to $p = (d^2-2ad+b^2-2ab+2a^2)(d^2-2cd+2c^2-2bc+b^2)$ ? I assumed that this polynomial above does not ...
0
votes
1answer
71 views

Primes $n=\overline{10101\cdots01}$ with $k$ ones.

Find all primes $n=\overline{10101\cdots01}$ with $k$ ones. The number is in standard base 10.
0
votes
1answer
93 views

Inequality with floor function (involving sum of the first $n-1$ primes)

Can we somehow prove that this holds: $p_n>$$\lfloor$$ 2(\sum_{i=1}^{n-1}p_i)\over n-1$$+1\rfloor$, for $n\geq5$, and $p_i$ is the i-th prime number?
0
votes
1answer
200 views

Using Prime numbers to map n integers uniquely to an integer x and allowing an easy reverse mapping

Say I have m integers: $i_{0}, i_{1}, ..., i_{x}, ..., i_{m} where -L < i_{x} < M$ where L and M are known integers is it possible to come up with a function that uses Primes that maps ...
1
vote
1answer
61 views

Counting primes of the form $S_1(a_n)$ vs primes of the form $S_2(b_n)$

Let $n$ be an integer $>1$. Let $S_1(a_n)$ be a symmetric irreducible integer polynomial in the variables $a_1,a_2,...a_n$. Let $S_2(b_n)$ be a symmetric irreducible integer polynomial in the ...
1
vote
1answer
74 views

Residue Classes

I am trying to show that: $$\sum\limits_{\beta \in \mathbb{Z}_p^*}{\beta^{-1}}=\sum\limits_{\beta \in \mathbb{Z}_p^*}{\beta}=0$$ Where p is an odd prime. I really dont know where to start, but my ...
4
votes
1answer
174 views

Functional Prime Sums

Let $ f: \mathbb{N} \to \mathbb{N} $ be a number-theoretic function satisfying $ f(xy) = f(x) + f(y) $ whenever $ \gcd(x,y) = 1 $. How can I prove that $$ \sum_{\substack{p ~ \text{prime}; \\ p \leq ...
1
vote
1answer
44 views

what is the property of this numbers

A multiple of $3$ gives $0,3,6,9,12,15,18,21,24,27$ which rearrange the last bit of each number gives $0,1,2,3,4,5,6,7,8,9$ once. The same can be said of $7$ and $9$ as well which gives ...
12
votes
2answers
475 views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
4
votes
1answer
571 views

Fermat's Little Theorem and Polynomial Congruence Relation

According to this Wikipedia article, we know that an integer $n\; (\geq 2)$ is prime if and only if the polynomial congruence relation $$ (x - a)^n \equiv (x^n - a) \pmod{n} $$ holds for all ...
8
votes
2answers
118 views

$R$ with an upper bound for degrees of irreducibles in $R[x]$

One very convenient property of $\mathbb{R}$ as a ring is that there is an upper bound for the degree of irreducible polynomials in $\mathbb{R}[x]$, as If $f\in\mathbb{R}[x]$ has degree larger ...
15
votes
1answer
1k views

If the abc conjecture has been proven what implication does that have for elliptic curve cryptography?

I am not a mathematician, but I was wondering if the proposed proof of the abc conjecture (PDF) by Shinichi Mochizuki of Kyoto University would contain insights and mathematical tools that would lead ...