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
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 ...
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 ...
10
votes
3answers
60 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 ...
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 ...
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
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 ...
10
votes
0answers
170 views

Are my calculations of a new constant similar to Mill's constant based on $\lfloor A^{2^{n}}\rfloor$ and Bertrand's postulate correct?

As Wikipedia explains in number theory, Mills' constant is defined as: "The smallest positive real number $A$ such that the floor function of the double exponential function $\lfloor A^{3^{n}}\...
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 ...
1
vote
1answer
118 views

Possible divisors of $s(2s+1)$ follow up question.

This question is related to this post:Possible divisors of $s(2s+1)$. I have some follow up questions which should be a new post. I write $\psi(s) = s(2s+1)$. We showed that for every prime $s$ that ...
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 ...
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 ...
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$ ...
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$?
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}$
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$?
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
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 ...
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
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{...
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 ...
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
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 ...
3
votes
0answers
344 views

The Divisors of $s(2s+1)$ and Primes $2n+1$ and $3n+1$ part 1

I want to check my math (and proof) on the following claim. The claim is by way of a computer search and a "hunch". claim: If $s$ is a prime number I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be ...
1
vote
1answer
84 views

Divisors of $s(2s+1)$ and the primes $s^2+1$

I need help proving that $s^2+1$ is prime in the following claim. claim: If $s$ is any positive integer I write $f_s =s(2s+1)$. I will need the divisor counting function $\tau$. Suppose that $...
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 ...
2
votes
1answer
49 views

Show that the cube roots of three distinct prime numbers cannot be three terms (not necessarily consecutive) of an arithmetic progression

I'm thinking we could do a contradiction, maybe showing that one of the primes is a composite number if they are in a sequence, but I'm not sure how to finish this up. I had this as a math problem in ...
1
vote
1answer
41 views

Is the Euler prime of an odd perfect number a repunit, or otherwise?

Let $N = {q^k}{n^2}$ be an odd perfect number given in Eulerian form (i.e., $q$ is prime with $\gcd(q,n)=1$ and $q \equiv k \equiv 1 \pmod 4$). (That is, $2N=\sigma(N)$ where $\sigma$ is the ...
3
votes
0answers
40 views

How to show that for $n$ sufficiently large, relative to $k$, $(n+1)(n+2) \ldots (n+k)$ is divisible by at least $k$ distinct primes

I would like to show that $\displaystyle \frac{(n+k)!}{n!}$ is divisible by at least $k$ distinct primes whenever $n$ is sufficiently large. We all know that it is divisible by $k!$ and hence by $\...
1
vote
1answer
23 views

Generate Sieve of Eratosthenes without “sieve” (generate prime set in interval)

How do I generate a list of primes based on the Sieve of Eratosthenes? I mean by excluding the divisible numbers beforehand, which is tricky for large numbers. I am an number theory amateur, but was ...
4
votes
1answer
23 views

Turing Decryption Example

I know this exact same question exists but I am still having problems in understanding it. The following is given in the text: The message m can be any integer in the set {0,1,2,…,p−1}; in par­...
0
votes
2answers
49 views

proving theorem about perfect powers

Im currently studying the journal entitled Perfect Powers with All Equal Digits but One theorem: For a fixed integer $l \geq 3$, there are only finitely many perfect $l$-th powers all whose digits ...
2
votes
2answers
76 views

Enumeration of primes

Given a prime number $p$, there is an associated number $n(p)$, giving its ranking in the sense that $n(2)=1$, $n(3)=2$, $n(5)=3$ etc. Is there a closed form expression for $n(p)$ in terms of $p$?
2
votes
3answers
58 views

The arithmetic function $\lambda(n)=(-1)^{a_1+\cdots +a_k}$

Define $\lambda(1)=1$, and if $n=p_1^{a_1}\cdots p_k^{a_k}$, define $$\lambda(n)=(-1)^{a_1+\cdots +a_k}$$ How can I see that $$\sum_{d\mid n}\lambda(d)=\begin{cases} 1 \,\,\text{ if $n$ is a square}\\...
1
vote
1answer
73 views

Conjecture concerning modular arithmetic

Below $0\notin\mathbb N$. I want a proof or a counter-example of the following (corrected) conjecture: Suppose $p$ is the smallest prime dividing $n\in\mathbb N$ and suppose $kn+ap=m!$, where $...
1
vote
0answers
57 views

The Porsche prime

A friend told me that the number starting with 911 followed by 911 zeros ending with 119 (that is $911\cdot 10^{914}+119$) is a prime number, the so-called Porsche prime. Maple indeed confirms that ...
0
votes
1answer
13 views

Existence of a Repeating Divisor

I have $n$ integers $a_1, a_2, a_3, .., a_n$ let $X = a_1*a_2*a_3*...*a_n$. I want to know a single integer $F$ such that $F^2$ divides $X$. It is told that there will be atleast one such $X$ and ...
1
vote
1answer
51 views

Why is it not known if Mill's constant is rational or irrational?

The following text appears in the Mill's constant definition at the Wikipedia: There is no closed-form formula known for Mills' constant, and it is not even known whether this number is rational (...
1
vote
2answers
55 views

The eventual advantage of a primality test without known exceptions

The primality test of Fermat with base $2$ seems to be as secure as the computer hardware for testing numbers big enough. However, I think there are an infinite numbers of false primes using this ...
4
votes
1answer
133 views

Is the Fermat primality test secure enough for very big numbers?

The random variable $X_m$ is the number of trials before $n\notin\mathbb P\wedge n|2^{n-1}-1$ where $n$ is an odd random integer $2^{m-1} < n < 2^m$. Computer simulations makes me believe ...
3
votes
1answer
43 views

Proving a number is Carmichael

here is my question: Let $p>3$ be prime, s.t $q = 2p-1$ and $g = 3p-2$ are primes as well. (For example $p=19$,$13$,$7$). Prove that $N = pqg$ satisfies $p-1|N-1$, $q-1|N-1$ and $g-1|N-1$. I ...
0
votes
0answers
30 views

Describe the prime elements of the ring $\mathbb Z[\sqrt{-2}]$ [duplicate]

I have a ring $\mathbb Z[\sqrt{-2}]$ and I need to describe all the prime numbers of that ring. How I can do that? Thank you