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
2answers
117 views

Primes in the binomial transform of $ [1, 1, 2, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, …]$.

This question is related to this sequence A139482. A commentator gives the following formula for $a_m$ $$a_m = {3m^2-9m+10 \above 1.5pt 2}$$ I have that you should consider the sequence $b_n =3n+2$ ...
0
votes
0answers
47 views

Is a tight concrete bound for the error-term in the prime-number-theorem known?

Here : https://en.wikipedia.org/wiki/Prime_number_theorem it is mentioned that $$\pi(x)=Li(x)+O(xe^{-a\sqrt{ln(x)}})$$ What is a tight upper bound for $|\pi(x)-Li(x)|$ in concrete terms ? The ...
11
votes
2answers
190 views

Two randomly chosen coprime integers

This is a twist on the problem commonly known to have solution $6/\pi^2$. Suppose when choosing from all natural numbers $\mathbb{N}$, the probability of choosing $n \in \mathbb{N}$ is given by $P(n)=...
3
votes
2answers
112 views

characterisation of $n$ as prime using min values of $x$ such that $nx+1$ or $nx$ is square

Let $n\ge 5$ be an odd integer and $k\ =\ \min\{x\in\mathbb{N}\colon nx+1\text{ is a perfect square}\}$ $l\ =\ \min\{x\in\mathbb{N}\colon nx\text{ is a perfect square}\}$ Prove that $n$ is a prime ...
1
vote
0answers
48 views

a consequence of Prime Number Theorem

By Prime Number Theorem we have $\lim_{n\to\infty}\frac{p_{n+1}}{p_n}=1$, so $\frac{p_{n+1}}{p_n}=1+a_n$ where $a_n\to 0$. How fast does $(a_n)$ converge to $0$ ? Does for example $a_n\ln n$ or $...
3
votes
1answer
168 views

Generalization of Inkeri's primality test

How to prove that following hypothesis is true ? Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are ...
3
votes
1answer
62 views

Longest sequence of primes where each term is obtained by appending a new digit to the previous term

What is the longest known sequence of primes where each new term is obtained by appending a new decimal digit to the previous term? Examples: $$(2,23,233,2333,23333)$$ There are no more members in ...
3
votes
0answers
98 views

How to test if $n!+1$ is prime or not?

for $n=0,1,2,3,11,27,37,41,73,77,116,154,320,340,399,427,872,1477,6380,26951,...$ $$n!+1$$ is prime. But how can you proof (with 100% certantiy) thats the case? Especially for the larger ones. For ...
1
vote
1answer
66 views

For every prime $p > 3$ that is $3$ mod $4$, does $q+1 \mid p-q$ for some other prime $q$?

Yet another random conjecture about primes: Given a prime $p>3$ of the form $4n+3$. Then there exist a prime $q<p$ such that $q+1\mid p-q$. Verified for all $p<100000$.
-1
votes
1answer
81 views

Is there any formula which gives better approximation than this formula?

Let $g(n),f(n)$ be functions of $n \in \mathbb{N}$. $g(n)=(n−1)^\frac{1}{n−1}$ $f(n)=\frac{a(g(n)^n)+(g(n)+(\frac{b}{n}))^n}{2}$ $P(n)=(f(n))\log_e (f(n))$ $P(n)$ gives the $n$th Prime Number. $a=...
1
vote
1answer
25 views

Anti-associativity of product of sum of squares

$\newcommand{\P}{\mathbb{P}}$$\newcommand{\Z}{\mathbb{Z}}$ Let $\P$ be the set of prime numbers congruent to $1 \pmod 4$. I know that for every $p \in \P$ there's a unique couple $(a^2,b^2)\in \Z^2$ ...
2
votes
0answers
45 views

Heegner Prime visualizations

The Heegner numbers are 1, 2, 3, 7, 11, 19, 43, 67, 163. The ring of integers $\textbf{Q}(\sqrt{-d})$ have unique factorizations. 1 gives the Gaussian integers. 3 gives the Eisenstein integers. 7 ...
0
votes
3answers
54 views

No primes in $f(n) = n(n+3)/2$ except 2 and 5

How can I prove that the sequence $f(n) = n(n+3)/2 = 0, 2, 5, 9, 14, 20, 27, 35, 44, ...$ does not contain primes except $2$ and $5$?
-2
votes
1answer
52 views

Is this possible to solve? [closed]

If a, b, c are different prime numbers such that (a-b)(a-c) = 255, find the value of b + c.
3
votes
2answers
210 views

Percentage of Composite Odd Numbers Divisible by 3

What is the percentage of odd composite positive numbers divisible by 3? In that same vein, what is the percentage of odd composite positive numbers divisible by 5? And, for the future, what is the ...
15
votes
3answers
1k views

A condition for being a prime: $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$

If $\;p=m+n$ where $p\in\mathbb P$, then $m,n$ are coprime, of course. But what about the converse? Conjecture: $p$ is prime if $\;\forall m,n\in\mathbb Z^+\!:\,p=m+n\implies \gcd(m,n)=1$ ...
2
votes
1answer
29 views

How to count the number of perfect square greater than $N$ and less than $N^2$ that are relatively prime to $N$?

I know a little about Euler's totient function that counts integer less than $N$ that are relatively prime to $N$. But I don't know how to modify the function for perfect square numbers, or maybe ...
0
votes
0answers
30 views

Finding a primes combination of a number

Okay. So I wanted to do a simple program which would take a number from the user, and then it would list all the combinations (multiplications) of a prime numbers or their powers, which would give the ...
10
votes
3answers
59 views

Calculate the number of integers in a given interval that are coprime to a given integer

We can calculate the number of integers between $1$ and a given integer n that are relatively prime to n, using Euler function: Let $p_1^{\varepsilon1}\cdot p_2^{\varepsilon2} \cdots p_k^{\varepsilon ...
9
votes
0answers
91 views

For any $x\in \mathbb{N}$ does there exist $m\in \mathbb{N}$ such that $2x+1+2m, 2x+1+4m$ are both prime?

Could someone please give me a proof (or counter example) for this (I believe it is true): For any $x$ (Whole Number) there exists some $m$ (Also Whole) such that $2x+1+2m$ and $2x+1+4m$ are both ...
0
votes
3answers
55 views

Understanding the sieve of eratosthenes

Wikipedia, explains the basic algorithm of eratosthenes and several pages such as this, explain the refinements made on the sieve. But the thing I'm having a hard time to find is: Why does the next ...
5
votes
2answers
101 views

Why does this pattern occur when using modular arithmetic against set of prime numbers?

I have been recently playing around with number theory and going through the project Euler problems. So I am very new to a lot of these things. I apologize for not knowing how to look up my answer. ...
40
votes
4answers
4k views

How far is the list of known primes known to be complete?

So there is always the search for the next "biggest known prime number". The last result that came out of GIMPS was $2^{74\,207\,281} - 1$, with over twenty million digits. Wikipedia also lists the ...
3
votes
1answer
68 views

Does a sequence based on hereditary factorisation always terminate?

The well-known Goodstein sequences are based on the hereditary base-$b$ notation, where you don't just present the digits in base $b$, but also the corresponding exponents etc. That lead me to the ...
0
votes
1answer
45 views

What is the equivalent statement of GRH in term of Redheffer Matrix or Farey Sequences?

We all know that Riemann Hypothesis (RH) has many equivalent statements. There is one statement which expresses RH in term of Redheffer matrix, there is another equivalent statement of RH which ...
0
votes
0answers
13 views

Effective estimates for k-almost primes

Given an integers $k$ and $\ell$ and a real numbers $\varepsilon>0$, define $f(k,\ell,\varepsilon)$ as the least $x_0$ such that for all $x>x_0$ the fraction of $\ell-$rough numbers up to $x$ ...
0
votes
0answers
70 views

Primality test for $F_n(10)=10^{2^n}+1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Theorem Let $F_n(2)=2^{2^n}+1$ ...
0
votes
1answer
31 views

Does there exist a closed-form expression for the following function?

I would like to find a closed-form expression for the function that is defined as follows: $T_{s}(x) = x^{s}(1 - x^{s}), \text{for prime } x \\ T_{s}(x) = x^{s}, \text{otherwise}$
3
votes
3answers
103 views

Can this upper bound for $\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor, p_i \in \Bbb P$ be improved?

I would like to find the smallest possible upper bound for the following sum of prime radicals (OEIS A062048): $\sum_{i=1}^n \lfloor \sqrt{p_i} \rfloor, p_i \in \Bbb P$ This is my attempt. It ...
5
votes
5answers
158 views

Prime divides $n^2 + 1 \Rightarrow$ prime doesn't divide $n$

How can I show that if a prime $p$ divides $$n^2 + 1$$ then it doesn't divide $n$?
5
votes
0answers
43 views

Explaining difference between natural numbers, integers, rationals, reals, complex numbers, Gaussian integers [closed]

As so far as usage in elementary number theory goes, what is the difference between the natural numbers, the integers, the rational numbers, the complex numbers, and the Gaussian integers?
0
votes
1answer
45 views

Finding the product of a prime function…

If we take the primes $p_k < n$, and raise them to the highest power possible such that $(p_k)^{r_k} \le n$, what is the lower bounds on $\prod{ (p_k)^{r_k} }$? In other words, what are the ...
1
vote
2answers
40 views

Existence of a prime number between $x$ and $y$ if $\operatorname{li}(y) - \operatorname{li}(x) = 1$

Is between $x$ and $y$ ($x < y$), there is always at least one prime number (or exactly one?) if $\operatorname{li}(y) - \operatorname{li}(x) = 1$?
6
votes
0answers
61 views

The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
0
votes
0answers
41 views

Is this reasoning of Chinese Remainder Theorem correct?

Originally I want to prove $y^{p'} \equiv x^n + C \pmod p$ is always having integer solution for some prime $p$ and $p'$ It is given by my classmate, so I do not know if it can really be proved, but ...
1
vote
3answers
36 views

Prove that if $p$ is a prime, then $p$ is a factor of $\binom{p}{r}$ for $r=1,2,\dots,p-1$ by using induction.

Prove that if $p$ is a prime, then $p$ is a factor of $\binom{p}{r}$ for $r=1,2,\dots,p-1$ by using induction. First, $\binom{p}{1}=p$. So it is clear that it has factor $p$. Suppose that $\binom{p}{...
1
vote
2answers
74 views

Are there any two identical terms in this series, defined parallely to the primes? [closed]

Let $p_n$ denote $n$-th prime number and $k_n$ be sequence that is \begin{align} k_1 &= 1 \\ k_2 &= p_2 - k_1 &&( 3-1 = 2 ) \\ k_n &= p_n - k_{n-1} &&\text{( n is integer ...
14
votes
1answer
714 views

How many digits of the googol-th prime can we calculate (or were calculated)?

Here, a lower and upper bound for the $n$-th prime are given. Applying the given bounds $$n(\ln(n\cdot\ln(n))-1)<p_n<n\cdot\ln(n\cdot\ln(n))$$ and the approximation $$p_n\approx n(\ln(n\...
1
vote
2answers
63 views

Numbers $a$ such that if $a \mid b^2$ then $a \mid b$

I want to describe the set of numbers $a$ such that if $a \mid b^2$ then $a | b$ for all positive integers b using the prime factorizations of $a$ and $b$. What would be a good way to approach this ...
1
vote
0answers
49 views

Upper bound for prime counting function $\pi(x)$

Let $\pi(x)$ denote the number of primes less than or equal to $x$. I want to prove $$ \pi(x) \leq \frac{9x\log 2}{\log x} $$ for every integer $x\geq 2$. In the problem (from Murty's $\textit{...
5
votes
3answers
120 views

Find $n$ with $100<n<2000$ such that $2^n+2$ is divisible by $n$?

Find a number $n$ with $100<n<2000$ such that $2^n+2$ is divisible by $n$ ? Its can easily be seen that $n=6$ is possible case but it does not satisfy the main constraint of being greater than $...
0
votes
0answers
25 views

Pollard's $\rho$ algorithm and quadratic sieve

I am wondering why is quadratic sieve better than Pollard's $\rho$ for integer of $10^4-10^{10}$ digits? The running time of quadratic sieve is $e^{(1+o(1))\sqrt{\ln n\ln \ln n}}$, but the Pollard's $\...
1
vote
1answer
55 views

What is the exact procedure to represent any positive integer '$n$' in the $m-adic$ form?

I've just started graduate number theory.This seems to be an elementary question,but i'm not getting exact procedure to represent any positive integer '$n$' in the $m-adic$ form. In particular,what ...
1
vote
3answers
41 views

Prove that there exists n consecutive composite numbers

I'm asked to prove that there exists n consecutive composite numbers. This is what I've come up with. $$n! + 1 = (1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \dotsc \cdot n) + 1 $$ is a prime number ...
0
votes
1answer
34 views

Characterization of primes $(6n+1, 6n-1)$ that are not twins

According to OEIS Sequence A002822(https://oeis.org/A002822), it states that $6n+1$ is a twin prime $iff$ $n$ is not of the form $6ab \pm a \pm b$. I was wondering if anyone had a proof for this. ...
4
votes
1answer
63 views

Proof of primes of the form $6n+1$

According to OEIS Sequence A002476 (https://oeis.org/A002476), it says that all primes of the form $6n+1$ can be written in the form: $x^2 - xy + 7y^2$ with $x$ and $y$ non-negative. I was wondering ...
10
votes
0answers
125 views

Finding $1/x^2 + 1/x^3 + 1/x^5 + \dots $

The following function came up in my work: $$ f(x)=\sum_{p\text{ prime}}\frac{1}{x^p}=\frac{1}{x^2}+\frac{1}{x^3}+\frac{1}{x^5}+\frac{1}{x^7}+\frac{1}{x^{11}}+\cdots. $$ Naturally, this converges for ...
8
votes
0answers
65 views

Number of primitive roots mod $p$ that are not primitive roots mod $p^2$

Consider the primitive roots of a prime $p$ in the range $1...p$ which are not primitive roots mod $p^2$. Let $n(p)$ be this number. While looking for an answer to this question, it seems that the ...
1
vote
0answers
37 views

Set of primetwins below 30

The Subset $C$ of the primes between 1 and 30, which have at least one primetwin (eg. 11,13). Would this be correct? $C=\{x\in \mathbb{N}\backslash\{1\} :(\nexists a\in \mathbb{N}\setminus\{1,x\}(a\...
1
vote
1answer
45 views

Asymptotics of $\sum\limits_{n/2 < p \leq n} \frac{1}{p}$

I'm reading a paper which asserts the following: $$\sum_{n/2 < p \leq n} \frac{1}{p} \sim \frac{\log 2}{\log n}$$ follows from prime number theorem, where the sum is taken over $p$ prime. What is ...