# 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.

12,147 questions
Filter by
Sorted by
Tagged with
20 views

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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
64 views

4k views

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 \... 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_{\... 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 ... 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 \... 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 ... 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 \... 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 ... -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? 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 ... 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 ... -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. ... -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 ... 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 ... 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 ... 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, ... 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 ... 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 ... 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 ... -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. ... 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 ... 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 ... 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 ... 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 ... 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 ... 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{\... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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=...
1 vote
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 ...