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

36
votes
1answer
852 views

Estimate for $n$th prime

A good approximation I have found for $p_{n}$ is \begin{align} \int_{2}^{n}\log (x \log (x \log (x)))\ dx\\ \end{align} and seems to be a better estimate than $n \log (n)$. The error term seems to ...
0
votes
1answer
18 views

Finding a module for the series $2^{i}$ from 0 to 219

How can I compute this: $\{ \sum 2^{i}$ for $i \in [0, 219] \} \pmod{13}$ I tried to manipulate the series by using the root principle to find the number of elements divisible by every prime $\leq ...
1
vote
1answer
26 views

$S=\{0,1,2,…,q^2-1\}$, is there a way to figure out how many elements contained in $S$ can be written as the sum of $2$ squares?

I'm currently working on a proof, and have broken it down into a series of problems. I've had success with every part except one. My question is (and it may be really easy; it's getting late): 'Let ...
4
votes
1answer
136 views

Does every record of the arithmetic derivative of natural numbers occur at a practical number?

Consider the arithmetic derivative of natural numbers, as defined here. By this definition, for every integer $n>1$, with canonical prime factorization ...
1
vote
1answer
30 views

Is it easier to find $a^2-8c=b^2$ than $a^2-c=b^2$

I found a way to factor numbers if I find: $$a^2-8c=b^2$$ Where $c$ is the number I want to factor Is it easier than searching for the next equation? $$a^2-c=b^2$$
1
vote
0answers
53 views

How to find integer solutions for $ax^2 + bx + c$

I am working on Integer factorization problem and I came to this: $$a = \frac{1-2b+\sqrt{4b^2 + 4b + 8c + 1}}{4}$$ c is the number that I want to factor $2a -1$, $a+b$ are factors of $c$ How to ...
5
votes
0answers
144 views

Primes of the form $\frac{n^2-n+4}{2}$ satisfy Hardy-Littlewood analogue?

Let $n,a,b$ be positive integers with $a<b$. Consider primes of the form $f(n)=\dfrac{n^2-n+4}{2}$. Let $C(a,b)$ denote the amount of primes of the form $f(n)$ between (and including) $f(a)$ and ...
10
votes
3answers
403 views

$\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges or diverges?

We will denote the set of prime numbers with $\mathcal P$. We know that the sum $\sum_{n=1}^{\infty}\frac1n$ and $\sum_{n=2}^{\infty}\frac1{n\ln n}$ diverges. It is also known that $\sum_{p \in ...
0
votes
2answers
87 views

Congruences and Primes

Show that if $p$ is an odd prime, with $p = 3 \pmod{4}$, then $$ (\mathbb{Z}_{p}^{*})^4 = (\mathbb{Z}_{p}^{*})^2 $$ More generally, show that if $n$ is an odd positive integer, where $p = 3 ...
0
votes
1answer
41 views

If $2^{k} + 1$ is prime, prove that $k$ has no other prime divisors than $2$. [duplicate]

I am trying to prove this by contradiction: Assume $2^{k} + 1$ is prime. By definition of odd number $2^{k} + 1$ is odd because $2^{k} + 1 = 2\cdot 2^{k-1} + 1$ Then $2^{k} + 1 \pmod{2} \equiv 1 ...
1
vote
0answers
24 views

Does this approach for factorizing RSA numbers help in any way?

I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
1
vote
1answer
74 views
+50

Density of primes in a polynomial

Consider that $p(x)$ is an irreducible polynomial with integer coeficients, that $\mathrm{gcd}$ of its coefficients is $1$. What is the natural density of the below set? $$A = \{n\ |\ p(n)\ \text{is ...
0
votes
3answers
32 views

Proving if $p|ab$ then $p|a\vee p|b$, then $p$ is prime

Let $1\neq p\in \mathbb N$ such that $\forall a,b \in \mathbb N$ if $p|ab$ then $p|a\vee p|b$. Prove that $p$ is prime. My attempt, proof by contradiction: Suppose $p$ isn't prime, then ...
-2
votes
1answer
89 views

Prove $x^{p^2-1}\equiv1\pmod{p^2}$ has exactly $p-1$ solutions for prime $p$ [on hold]

Let $m=p^2$ where $p$ is a prime number. Show that the congruence $x^{m-1}\equiv 1\pmod{m}$ has precisely $p-1$ solutions. Let $m = pq$ where $p$ and $q$ are distinct prime numbers. Show that then ...
2
votes
1answer
52 views

Existence of solution to Congruence relation $(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$

I'm taking the final exam in "Number Theory" tomorrow and stuck with: Prove that $\,\,\forall p\in\mathbb{Z}_p\,$ the congruence relation: $$(x^2-2)(x^2-6)(x^2-3) \equiv 0\pmod p$$ has a ...
0
votes
1answer
32 views

Integer factorization simplification

I found a small improvement to the brute force algorithm for the Integer Factorization. Please tell me if there is a point to investigate it more or there are better similar ideas. I found that if ...
2
votes
2answers
123 views

prime factors of number with a particular form

I try to factorize this huge number $2^{(3^{(5^7)})} +7^{(5^{(3^2)})}$ .but i have no idea,the only thing i know is that it's not divisible by 7 and 11. can you help me find some prime factors of ...
1
vote
1answer
45 views

On the prime number theorem in shorts intervals

In 1988 Heath-Brown (" The number of primes in a short interval ", J. reine angew. Math. 389, 22-63) proved this theorem: Let $\varepsilon\left(x\right)\leq\frac{1}{12}$ be a non-negative function ...
1
vote
1answer
23 views

existence of solution to congruence $x^4 \equiv -4 \pmod p$

I stuck with the following question: For which $p$ (prime numbers) there is a solution for the following congruence: $x^4 \equiv -4 \pmod p$ I would greatly appreciate any help
13
votes
8answers
1k views

Does the formula $\sqrt{ 1 + 24n }$ always yield prime?

I did some experiments, using C++, investigating the values of $\sqrt{1+24n}$. ...
5
votes
2answers
301 views

If $m^4+4^n$ is prime, then $m=n=1$ or $m$ is odd and $n$ even

I have been stuck on this one for months, really simple to state, really giving me trouble. Show that if $m^4 + 4^n$ is prime, $m>0$, $n>0$, then $m$ is odd and $n$ is even, except when ...
1
vote
1answer
40 views

Asymptotic expression for $3$ term arithmetic progression in the primes

I have found an asymptotic for the following sum using the circle method: \begin{align} R(n)=\sum_{\substack{p_1,p_2,p_3 \le n \\p_1+p_2=2p_3 }} \log (p_1) \log (p_2) \log ...
1
vote
0answers
23 views
+100

Let $g_n^k=p_{n+k}-p_n$, where $p_n$ is the $n$th prime. Does there exist $g_{k+1}^1=2$ such that $g_1^k,g_2^k,\ldots$ is a “Gilbreath sequence?”

Call $(S_i)_{i=1}^{\infty}$ a Gilbreath sequence if $1=\lvert S_2-S_1\rvert=\lvert \lvert S_3-S_2\rvert-\lvert S_2-S_1\rvert\rvert=\cdots$, i.e., if the sequence can be substituted for the primes in ...
2
votes
0answers
34 views

Short intervals with all numbers having the same number of prime factors

How to prove that for some $k, n_0$, for all $n \ge n_0$ it is never the case that all integers in $\{n, n+1, \dots, n + \lfloor (\log{n})^k \rfloor\}$ have exactly the same number of prime factors ...
1
vote
2answers
52 views

Prove that $\sum_{p \in \mathcal P} \frac1{p\ln \ln p}$ is divergent

In this question I've asked to decide the convergency of the series $\sum_{p \in \mathcal P} \frac1{p\ln p}$. Now I ask you to show that the series $$\sum_{p \in \mathcal P} \frac1{p\ln \ln p}$$ ...
0
votes
1answer
30 views

prove that $p^2-1$ is divisible by $24$ if $p$ is a prime greater than $3$ [duplicate]

How to prove that $p^2-1$ is divisible by $24$ if $p$ is a prime number greater than $3$?
5
votes
2answers
346 views

RSA encryption. Breaking 2048 keys with index

I have some thoughts on this. First, I want to say I am no expert on cryptography, I just know some stuff, and I took a cryptography class in University. I am very interested in this topic. I ...
36
votes
2answers
1k views

Prime powers, patterns similar to $\lbrace 0,1,0,2,0,1,0,3\ldots \rbrace$ and formulas for $\sigma_k(n)$

Some time ago when decomponsing the natural numbers, $\mathbb{N}$, in prime powes I noticed a pattern in their powers. Taking, for example, the numbers $\lbrace 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
1
vote
6answers
2k views

“Question: Show that $n^5 - n$ is divisible by 30; for all natural n” [duplicate]

Show that $n^5 - n$ is divisible by $30;$ $\forall n\in \mathbb{N}$ I tried to solve this three-way. And all stopped at some point. I) By induction: testing for $0$, $1$ and $2$ It is clearly ...
0
votes
2answers
49 views

Understanding why the public exponent $e$ is chosen the way it is in RSA

I am trying to get a better understanding of RSA. At the moment I am unable to understand the difference between the correctly chosen value of the public exponent $e$ and other possibilities ...
0
votes
1answer
36 views

If $p^q - 1$ is a prime, then $p=2$ and $q$ is a prime [duplicate]

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem : If $p$ and $q$ are positive integers ($\mathbb{Z}^+$) such that $q \gt 1$ and $(p^q - 1)$ is ...
2
votes
1answer
29 views

Asymptotic formula for sums related to primes

Suppose $0 < \alpha < 1$. What is the asymptotic formula for the sum $$\displaystyle \sum_{p \leq x} \frac{\log p}{p^\alpha}?$$ Thanks for any insights.
7
votes
1answer
210 views

Sum of a Sequence of Prime Powers $p^{2n}+p^{2n-1}+\cdots+p+1$ is a Perfect Square

Find all primes p such that $p^{2n}+p^{2n-1}+p^{2n-2}+\cdots+p^{2}+p+1$ is a square for some value of n.
0
votes
2answers
76 views

Exercise on Great Common Divisor and Prime Number [duplicate]

Let $p$ be a prime number and let $1 \leq n < p$ be a non-negative integer number. Show that there exist $x,y \in \mathbb{Z}$ such that $n x + p y = 1$.
3
votes
2answers
113 views

Is there an obvious reason why $4^n+n^4$ cannot be prime for $n\ge 2$? [duplicate]

I searched a prime of the form $4^n+n^4$ with $n\ge 2$ and did not find one with $n\le 12\ 000$. If $n$ is even, then $4^n+n^4$ is even, so it cannot be prime. If $n$ is odd and not divisible by ...
3
votes
0answers
78 views

How to prove this??

Does the following inequality hold? $p(n)\leq 2^n,$ where $p(n)$ is the $n$th prime. If this is true then it follows that: If $p(n)=p(m)^x+p(o)^y$, then $\max[x,y] \le n$.
1
vote
1answer
36 views

For how many integers is this a prime number?

For how many integers $n$ is: $9 - (n-2)^2$ a prime number? I want to try this using a rigorous definition of prime number/ actual problem rather than try-error? Please only give hints, so I can do ...
0
votes
2answers
50 views

Prove if $ord_p(d) < ord_p(n)$ then d divides n

I have to prove that $d$ divides $n$ if and only if $ord_p(d)\leq ord_p(n)$ I have already proved that $ord_p(d)\leq ord_p(n)$ if $d$ divides $n$ but I am struggling to prove the converse. Can ...
2
votes
0answers
34 views

Determine whether permutation of the digits of a number is prime

Given a number $m$ in decimal representation. I want to find a permutation of the digits of $m$, so it is prime. (Or output that there exists none) Do i have in the worst case check every possible ...
6
votes
8answers
4k views

Is zero a prime number?

Q: Zero is it a prime number? Q: Zero is odd or even? Q: Zero is a number? If yes or no, then why?
5
votes
3answers
439 views

Prime Number in triangle

I had a question here, the measures of the sides of a right triangle (a single unit) can be prime numbers? If they can not, why?! But, if you can, could you help me find an example?
0
votes
2answers
44 views

Sum of certain two-digit primes with prime digits

Let $P$ be a two-digit prime number less than $100$ such that both digits are prime numbers. What is the sum of all such numbers, $P$? Is there a quick way to solve this problem without listing all ...
1
vote
4answers
173 views

$(a^{n},b^{n})=(a,b)^{n}$ and $[a^{n},b^{n}]=[a,b]^{n}$?

How to show that $$(a^{n},b^{n})=(a,b)^{n}$$ and $$[a^{n},b^{n}]=[a,b]^{n}$$ without using modular arithmetic? Seems to have very interesting applications.$$$$Try: $(a^{n},b^{n})=d\Longrightarrow ...
1
vote
1answer
85 views

Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?

If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
3
votes
1answer
31 views

Origin of period function model of primes

There is a web page attributed to Omar Pol, "Sobre el patrón de los números primos: Determinación geométrica de los números primos y perfectos." ("On the pattern of primes: Geometric Determination of ...
3
votes
1answer
267 views

If two primes differ by $n$, then infinitely many primes differ by $n$

A proof I'm writing rests on something I can't prove, probably beyond my knowledge, but it seems right: For any two primes $p_k, p_l$ (not necessarily consecutive) such that the distance between ...
0
votes
3answers
59 views

Find values of $n$ that yield a prime number

Let $n$ be a positive integer, and $\frac{n(n+1)}{2}-1$ is a prime number. Find all possible values of n. What I have so far is this: $$\frac{n(n+1)}{2}-1=2, n=2$$ Also, $n^2+n-2\over2$ can be ...
4
votes
1answer
86 views

Trying to understand a step in Ramanujan's Proof of Bertrand's Postulate regarding the gamma function

My question relates to this step in the proof here: But it is easy to see that $$\log \Gamma(x)-2\log\Gamma(\frac12x+\frac12) \le \log\left\lfloor ...
1
vote
0answers
17 views

Understanding how to estimate $\pi(x)$ based on Paul Erdos's proof of Bertrand's Postulate

I am reading the 4th Edition of Proofs from the Book. I am not clear on how the proof behind Bertrand's postulate leads to the following statement on page 10 (of my edition): From (2) one can ...
1
vote
2answers
99 views

Problem of Ages (Problema das Idades)

English: Somebody help me with this challenge? It's very confusing: Today, both me and my younger brother are between $10$ and $20$ years old. Also, our ages are expressed by prime numbers and the ...