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

4
votes
0answers
145 views

Is the Wikipedia article on the proof for Bertrand's Postulate correct?

I was checking out the Wikipedia article on the proof of Bertrand's Postulate. For Lemma 4, the argument is made for $x\ge 3, x\#<2^{2x-3}$ Here's the proof by induction: $n = 3$: $n\# = ...
1
vote
2answers
165 views

For which prime numbers $p$ does the congruence $x^2 + x + 1 \equiv 0 \pmod{p}$ have solutions? [duplicate]

For which prime numbers p does the congruence $x^2 + x + 1 \equiv 0 \pmod{p}$ have solutions? We've recently learnt about quadratic reciprocity in class, however I am not sure how to tackle this ...
5
votes
1answer
67 views

Prime numbers making constant : 1.2527

Reading "Excursion in calculus" (Robert M. Young, 1992), exercice 13 on page 71 ask the reader to show there is a constant $c\approx 1.25$ such that $a_0=2^c$ $a_{n+1}=2^{a_n}$ $\forall n\; \lfloor ...
0
votes
1answer
20 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 ...
2
votes
1answer
46 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
204 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 $p_1^{a_1}p_2^{a_2}...p_{\omega(n)}^{a_{\...
1
vote
1answer
45 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$$
5
votes
0answers
157 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 $f(...
11
votes
3answers
534 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
97 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 \pmod{4}$...
0
votes
1answer
81 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
1answer
121 views

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
52 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 $\exists t\...
2
votes
1answer
80 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 solution....
1
vote
1answer
82 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 ...
1
vote
1answer
106 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
45 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
2k 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
353 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 $m=n=...
1
vote
2answers
75 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
66 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
414 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 ...
40
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
4k 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 true. ...
0
votes
2answers
71 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
45 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
41 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.
6
votes
1answer
293 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
79 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
136 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
89 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
46 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
95 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
69 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 ...
5
votes
3answers
502 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
88 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
188 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 d\...
1
vote
1answer
88 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
296 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
61 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
140 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 x\right\rfloor!-2\log\left\lfloor\frac12x\...
1
vote
2answers
123 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 ...
14
votes
2answers
401 views

Numbers that are divisible by the number of primes smaller than them

Let $\pi(n)$ denote the number of primes less than or equal to $n$ (a.k.a the prime-counting function). For certain values of $n$, the value of $\frac{n}{\pi(n)}$ is integer. Here are the first few ...
1
vote
3answers
547 views

“Goldbach's other conjecture” and Project Euler - writing 1 as a sum of a prime and twice a square

From Problem 46 of Project Euler : It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square. $$9 = 7 + 2 \cdot 1^...
3
votes
1answer
53 views

Prove for any integer $N$ that there exists $n > N$ where $n!-1$ is not a prime

I was thinking about Euclid's proof of the infinitude of primes and the fact that we could make the argument about $n!-1$ instead of $n!+1$ when I wondered if it would be easy to prove that for any $N$...
5
votes
1answer
91 views

Paul Erdős showed a simple estimate for $\pi(x) \ge \frac{1}{2}\log_2 x$; is it possible to tweak his argument to improve the estimate?

Paul Erdős gave a simple argument to show that $\pi(x) \ge \dfrac{1}{2}\log_2 x$. Is it possible to tweak the argument and get a better estimate? I am wondering how good an estimate for $\pi(x)$ can ...
5
votes
0answers
76 views

Which prime gaps are known to exist [duplicate]

It is easily proved that prime gaps can be arbitrarily large by constructing the sequence of composites $(n+1)! + 2, (n+1)! + 3, \dots, (n+1)! + (n+1)$, which are divisible by $2, \dots, n+1$ ...
1
vote
3answers
374 views

The gcd of $p+q$ and $p-q$ where $p4 and $q$ are distinct odd primes

Suppose $p$ and $q$ are distinct odd primes. Prove that $\gcd(p+q, p-q) = 2$. I had figured out that $d$ divides $2p$ and $d$ divides $2q$, but I did not recognize to use coprimeness and ...
4
votes
2answers
1k views

How many perfect squares divide 1!2!3!4!5!6!7!8!9!

What I naturally did was to find the prime factorisation of the product of factorials which is $ 2^{30}3^{13}5^5 7^3 $. Clearly there is 15 unique perfect squares that divide $2^{30}$, 6 unique ...
1
vote
2answers
105 views

How to recognise the digit multiplication, subtraction or addition when checking for divisibility by 7, 11, 13, 17 and 19?

I was studying this page Divisibility by prime numbers under 50 to check for the divisibility by 7, 11, 13, 17, 19 etc. Is there any way to recognise whether to add or sub the given times of unit ...