Questions tagged [prime-numbers]

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
20 views

A formula (or asymptotic) to count the number of square roots of unity modulo $d$ that are less than or equal to $t$?

Let $d$ be a square-free integer, though any formula (title question) may be more general than that. Define the residues of the square roots of unity modulo $d$ to be: $$ G_d := \{ x \in \{0, \dots, d-...
Daniel Donnelly's user avatar
3 votes
1 answer
77 views

Is there a pattern of grouping for prime numbers?

Consider all the natural numbers up to 1000 ending in the number n, which has a value in the set (1, 3, 7, 9). Calculate n^2-2 for each individual value of n up to 1000 and check if the result is ...
Betho's's user avatar
  • 141
3 votes
0 answers
69 views

Bizarre function that generalizes the inclusion-exclusion formula for $\pi(t) - \pi(\sqrt{t + 1})$. For all reals $t\geq 5$, the function is non-zero

Conjecture. The following arithmetic function is never zero, for any $t \in \Bbb{R}$, and $t \geq 5$: $$ g(t) := \sum_{d \mid p_n\#}(-1)^{\omega(d)}\left\lfloor\frac{t}{d}\right\rfloor|G_d| $$ where $...
Daniel Donnelly's user avatar
0 votes
0 answers
29 views

Sums of multiples of the two most recent primes

For all integers n > 3 there exists two integers 'a' and 'b' such that: n = a(Biggest prime smaller than n) + b(Second biggest prime smaller than n) Formal Logic Statement: ∀n ∈ {x ∈ ℤ : x > 3} ∃...
hefe's user avatar
  • 1
4 votes
0 answers
54 views

Good asymptotic for $\sum_{n=1}^{\infty} \frac{x^n}{p_n^{p_n}}$

Consider $$f(x) = \sum_{n=1}^{\infty} \frac{x^n}{p_n^{p_n}}$$ Where $p_n$ is the $n$ th prime. What is a very good asympotic $g(x)$ for this function as $x$ goes to $+\infty$ ? I want at least $$\lim_{...
mick's user avatar
  • 14.3k
3 votes
0 answers
85 views

Proving that there are infinite primes with digit sum 8 in base 10

I recently wrote about a problem I cam up with while thinking about number theory, which you can find on this post. Long story short, I'm trying to prove there are infinite natural numbers such that ...
Franci12's user avatar
1 vote
4 answers
59 views

How can we prove that $\lim_{x\to\infty}\left(\frac{\pi (x)}{x}-\frac{1}{\log x}\right)=0$?

The prime number theorem states that $$\lim_{x\to\infty}\frac{\pi (x)}{x/\log x}=1$$ where $\pi$ is the prime counting function (https://en.wikipedia.org/wiki/Prime-counting_function). In a YouTube ...
Vestoo's user avatar
  • 407
-1 votes
0 answers
38 views

Sum of prime factors function

I'm developing a function whose domain is only composite numbers except 4. What the function does is that it sums the prime factors of the given composite number until it results in a prime number as ...
Berke's user avatar
  • 1
-2 votes
0 answers
79 views

What's wrong with not considering primes as the "fundamental building blocks" of integers?

By a simple-minded reasoning, one could argue that prime numbers are not that special: integer multiplication can be reduced to addition, and, by successive additions of $1$ to itself, all integers ...
exp8j's user avatar
  • 275
1 vote
1 answer
35 views

Use Mersenne numbers to prove that there are infinitely many prime numbers.

When reading the book Mersenne Numbers and Fermat Numbers, after proving that: for any positive integers m,n, it holds $\gcd(M_n,M_m)=1$ if and only if $\gcd(m,n)=1$, it says that this allows us to ...
Lumos's user avatar
  • 101
1 vote
1 answer
64 views

Nonconstant polynomial $f(x) \in \mathbb{Z}[x]$ with $f(0)=1$, then there exists an $n \in \mathbb{N}$ such that $f(n)$ is divisible by 2021 primes.

I'm working on a problem which is stated as follows : Let $f(x) \in \mathbb{Z}[x]$ be a nonconstant polynomial with $f(0)=1$. Then, there exists $n \in \mathbb{N}$ such that $f(n)$ is divisible by $...
Oopsilon's user avatar
-3 votes
0 answers
32 views

Detailed proof of question below

Show that If p is an odd prime number,then every prime divisor of 2^p -1 is of the form 2pk+1 for some k belonging to Natural numbers.
Izad's user avatar
  • 1
3 votes
0 answers
48 views

Finding nice representation for a partial geometric sum

Everyone knows that (when $x<1$) $\sum_{n=1}^\infty x^n = \frac{x}{1-x}$. I was wondering if one can find a simple expression (i.e. without the sum) of $\sum_{n \in \langle p_1,...,p_k\rangle} x^{n}...
DIexp's user avatar
  • 130
28 votes
5 answers
4k views

How is the logarithm of an integer analogous to the degree of a polynomial?

I've recently been reading Serge Lang's Math Talks for Undergraduates, specifically a section about the abc conjecture. Lang starts by stating and proving the Mason-Stothers Theorem: Let $f,g \in \...
Adam Nelson's user avatar
0 votes
1 answer
47 views

Conjecture: It is not true that $2$ eventually always divides $f(x) = \sum_{d \mid p_{\sqrt{x+1}}\#} (d \mid x^2 - 1)$.

Lemma. Let $(d \mid \cdot ) : \Bbb{Z} \to \{0,1\}$ be whether $(1)$ or not $(0)$ $\ d$ divides the input. There exists no $N \in \Bbb{N}$ such that $\forall x \geq N$ we have $$f(x) = \sum_{d \mid p_{\...
Daniel Donnelly's user avatar
0 votes
1 answer
118 views

How to factor numbers like 8,023 manually

I was given a random 4-digit number to factor over the prime numbers. My number was 8,023. I tried applying all the divisibility rules up to 36 before giving up on them. I tried using algebra as ...
chroma's user avatar
  • 1,957
4 votes
1 answer
198 views

What's the idea of Dirichlet’s Theorem on Arithmetic Progressions proof?

Dirichlet’s Theorem on Arithmetic Progressions says that if $a, m$ are natural numbers such that $gcd (a,m) = 1$, then there are infinitely many prime numbers in the arithmetic progression $a + km, k \...
Nicolás A.'s user avatar
0 votes
0 answers
102 views

Riemann Hypothesis Research

I don't know if this is the correct place for this. If not feel free to remove! I am a recent graduate of a BSc in Applied and Computational Maths and am now not working in a maths field. I miss ...
Barry O'Keeffe's user avatar
3 votes
2 answers
184 views

Pairs promoting diversity

Let $p$ be a prime number at least three and let ${k}$ be a positive integer smaller than $p$. Given ${a}_1, \ldots, {a}_{{k}} \in \mathbb{F}_p$ and distinct elements ${b}_1, \ldots, {b}_{{k}} \in \...
Snowball's user avatar
  • 1,057
4 votes
0 answers
193 views
+50

Is the problem NP-hard?

Let $GF(p) = ({\mathbb Z}_p, +, \times)$ be the Galois field where $p>2$ is prime and let $$ H=\{1,2,\cdots, \frac{p-1}{2}\}.$$ I need an algorithm (subexponential in terms of $\log_2 p$) that ...
qwerty43's user avatar
  • 341
-1 votes
0 answers
14 views

What is the max length of an interval of consecutive multiples of a finite set of primes? [closed]

Given a set $\{p_1... p_n\}$ of primes, what is the maximum length of an interval $a , a+1, a+2, ..., a+m$ such that for any $a+i$, there exists a $p_j$ that divides it?
Carl Olimb's user avatar
0 votes
1 answer
44 views

Chebyshev’s theorem and Bertrand's postulate : An exercise .

The title of my question comes from here https://web.williams.edu/Mathematics/lg5/Chebyshev.pdf : Looks at the reference (link above) we have the following theorem : Chebyshev’s theorem : There exists ...
Erik Satie's user avatar
  • 3,440
1 vote
1 answer
45 views

How would one show that any given prime p_i must be a factor of some (p_j - 1)? Is that a true property of primes even? [closed]

In short, what I'm asking is, if you were to go through the whole set of positive primes term by term and find for each prime p the prime factorization of (p - 1), whether all prime numbers would ...
Sandy Andy's user avatar
-5 votes
1 answer
52 views

Is there a sieve that can be used to generate prime numbers for the formula produce by 6n±1, a trait of prime numbers greater than 3?? [closed]

I stumbled into a way to identify all the specific composite numbers for 6n+or-1. 6n(PN)±PN, where PN is a prime number greater than 3 and equal to or less than the square root of a targeted range. ...
Orlando Vidads's user avatar
-1 votes
1 answer
108 views

What is the fastest way to write an even number as the sum of two primes?

Assume Goldbach Conjecture and write an even number $2n$ as the sum of two primes. The obvious approach is the forward search: Start with $p=3$ and check if $2n-p$ is a prime. If yes, stops, else we ...
Nilotpal Sinha's user avatar
2 votes
1 answer
84 views

The set of all sums of 3 primes covers almost all of $2\Bbb{Z}+1$ (result of Helfgott), what can one say about $\Bbb{P} - \Bbb{P} = 2\Bbb{Z}$ problem?

Consider the set $\Bbb{P} = \pm$ the prime numbers and $\Bbb{P}_o$ is similarly $\pm$ the prime numbers other than $2$. By Helfgott's result on the ternary Goldbach conjecture: Every odd integer ...
Daniel Donnelly's user avatar
1 vote
1 answer
86 views

$\omega$ of a highly composite number.

A number is highly composite if it is the smallest number that has more divisors that any number less than it. Let $(h_n)_{n\ge 1}$ be the sequence of highly composite numbers and $\omega(n)$ denote ...
PNT's user avatar
  • 3,899
1 vote
1 answer
214 views

On the Second Hardy-Littlewood conjecture

I have recently known about the Second Hardy-Littlewood conjecture, and I was struck when I noticed that this conjecture was very related with this question I asked in this site. So, my question is, ...
Juan Moreno's user avatar
0 votes
0 answers
50 views

Representation of non zero rational number

I have seen the following representation of non zero rational numbers in course notes : $$ \forall r\in\mathbb{Q}\setminus\{0\},\quad r = p^{k}\frac{m}{n}\quad k,m,n\in\mathbb{Z} $$ where $p$ is a ...
coboy's user avatar
  • 906
0 votes
0 answers
22 views

Primes in quadratic rings that are not UFD's [duplicate]

In a quadratic ring $\mathbb{Z}[\sqrt{d}]$ that is not a UFD, is there a simple proof that if an element has a norm that is a prime integer, then that element of the ring is prime, not merely ...
akay's user avatar
  • 9
0 votes
0 answers
24 views

Proof that $L =$ {$a^p : \text{p is prime} $} is not regular

I know that this question has already been answered but the proofs provided do not seem intuitive to me and I propose one using Wilson's theorem. Say $L$ is regular and its pumping length is $p \geq ...
rookie_cookie's user avatar
-3 votes
0 answers
119 views

How do we know we can "enumerate the primes" in this proof of the infinitude of primes?

In the presentation my course notes give of Euclid's proof, it is mentioned that we could enumerate the primes given that there is a finite amount of them. I have a few questions about just this part. ...
God's user avatar
  • 816
0 votes
1 answer
54 views

Convergence for infinite sum of all primorials reciprocals.

I'm not math major, but I am interested in maths, and was at home thinking about primes, and thought about the quistion in the title. It might seem complex or kind of vague (I'm not a native english ...
Sejr's user avatar
  • 89
2 votes
2 answers
111 views

Is this a valid proof by contradiction for why there are infinitely many primes?

I would appreciate feedback on whether the specific contradiction I make is valid in my attempt to prove that there are infinitely many primes, this on a conceptual level. For context, I subsequently ...
God's user avatar
  • 816
2 votes
0 answers
45 views

An arithmetic problems

"Find all the positive integers $n$ satisfying $2^n+n^2 +25 = p^3$ where $p$ is a prime number." I proved that $n$ must be divisible by 6 and predicted $n=6, p=5$. However, I can't wrap it ...
Noun's user avatar
  • 31
1 vote
0 answers
64 views

Sequence regarding smallest prime divisors

My friend Agamjeet Singh came up with the following question: Let $\lambda(a)$ denote the smallest prime factor of $a$. Consider an infinite sequence $(a_n)_{n\geqslant 1}$ of positive integers such ...
oVlad's user avatar
  • 139
3 votes
4 answers
198 views

Generating residues with $ a^n + b^n \mod p $

Say there exist some non-zero distinct residues $a,b$ such that $$ a^n + b^n \mod p $$ generates all nonzero residues for some $n$. Does such a pair $a,b$ exist for every odd prime $p > 13$ ? Or ...
mick's user avatar
  • 14.3k
1 vote
2 answers
86 views

How to find the poles of $\frac{\zeta'(s)}{\zeta(s)}$?

When proving the theorem of prime numbers, the professor introduced a function $\phi(s)=\sum_{p}\frac{\log p}{p^s}$, where $p$ is all prime numbers. After a calculation, we get this formula: $$-\frac{\...
Ychen's user avatar
  • 317
0 votes
0 answers
94 views

solutions to $x = \sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$

Fix an integer $0<a<p-1$, and an odd prime $p$. Define $$S(a,p)=\sqrt{a+\sqrt{a+\sqrt{a+\cdots}}}\;\;(\text{mod}\;p)$$ to be the set of all integers $x\in\{0,...,p-1\}$ such that, for some ...
mick's user avatar
  • 14.3k
5 votes
0 answers
72 views

Is $5^1$ the maximal power of 5 that divides evenly into ${1000 \choose 500}$?

I am trying to solve an exercise from Hua Loo Keng's Introduction to Number Theory Chapter 1 Section 12 to further my understanding of the material. Here are the steps I took to arrive at this ...
Aadith Thiruvallarai's user avatar
0 votes
0 answers
87 views

Prime divisors of $f(n):=F_{n^2}+F_n+1$?

Let $F_n$ be the $n$ th fibonacci-number and define $$f(n):=F_{n^2}+F_n+1$$ For which positive integers $n$ do we have no small prime factor (say $p<10^7$) $p\mid f(n)$ ? Are there useful ...
Peter's user avatar
  • 81.1k
2 votes
0 answers
57 views

Finding prime numbers with mod function with respect to given odd number $'a'$ between $2^n$ and $2^{n+1}$

Here are few steps which made sense when analysing the prime numbers Step 1: For any odd number "$a \in Z^+ $" e.g. 17 Step 2 : $a$ is $2^{n} < a < 2^{n+1}$ Step 3: now get the list ...
Sivakumar Krishnamoorthi's user avatar
4 votes
1 answer
121 views

How well does $\mathrm{Zi}(x)=\frac1e\sum_{k=1}^\infty\frac{(\ln x)^k}{kk!\phi(k)}$, with $\phi(k)=\sum_{n=1}^\infty e^{-n^k}$, approximate $\pi(x)$?

It is well known that: $$\mathrm{Li}(x)=\int_2^x \frac{1}{\ln(t)}~dt$$ is an extraordinarily good approximation to the prime counting function $\pi(x)$ and is currently the best known approximation. I ...
geocalc33's user avatar
  • 372
1 vote
1 answer
89 views

Finding the (smallest) next number with the same distinct prime factors as a previous number

(Since there is no answer yet, I removed most "EDIT"'s to make the text more readable) Today, I was trying to find a natural number $n_{2}$ such that this number has the same distinct prime ...
questionmaster's user avatar
2 votes
1 answer
75 views

Does Euler product formula give any hints about asymptotics of primes?

From the Euler product formula for $\zeta$ function we get $$ \sum\limits_n\frac1{n^s} = \prod\limits_p\frac1{1 - p^{-s}} = \mathrm{exp}\left(-\sum_p\log(1 - p^{-s})\right). $$ As $s\to\infty$ we ...
SBF's user avatar
  • 35.2k
0 votes
0 answers
82 views

Prove that the prime numbers are eventually always worse than the natural numbers in the ability for their reciprocals to approximate $0.$

Let $n\in\mathbb{N},\ $ let $p_k$ be the $k-$th prime, let $[n]:= \{1,2,\ldots,n\},$ and let $ E:=\{-1,0,1\}.$ Let $x$ be the the least positive real number such that $\ x = \displaystyle\sum_{k=1}^{k=...
Adam Rubinson's user avatar
1 vote
1 answer
89 views

A problem on von Mangoldt function.

Suppose $n$ is odd natural number. Define $r(n)=\sum_{n_1+n_2+n_3=n} \Lambda(n_1)\Lambda(n_2)\Lambda(n_3)$ and $r'(n)=\sum_{p_1+p_2+p_3=n}(\log p_1)(\log p_2)(\log p_3)$ where $p_1,p_2,p_3$ are ...
Subhadip Chowdhury's user avatar
2 votes
1 answer
56 views

How to prove that $\sum_p\frac{\ln p}{p^s(p^s-1)}$ converges at $\Re\{s\} >1/2$?

I am trying to prove that $$\sum_p\frac{\ln p}{p^s(p^s-1)} = \text{const.} \qquad \Re\{s\} > 1/2,$$ where $\{p\}$ is a set of all primes. Mathematica shows that $$\lim_{x\to\infty}\frac{\ln x}{x^s(...
George's user avatar
  • 21
5 votes
1 answer
196 views

Are there infinite elements in the super prime set?

Background Define the following set, the initial elements are $\{2,3,5,7\}$. Then, repeat the following operations, if you add a digit to any position of any number in the set, the number is still a ...
GalAster's user avatar
  • 943
4 votes
2 answers
166 views

Show $\sum_p\frac{1}{p^{1+i}}$ converges

I am struggling with exercise I.15 in Tenenbaum's Analytic Number Theory book. The problem says to show that (here $\color{blue}{i}$ is the imaginary unit) $$\sum_{p}\frac{1}{p^{1+i}}$$ converges ...
Anon's user avatar
  • 457

1
2 3 4 5
243