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

0
votes
0answers
14 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
48 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$?
0
votes
0answers
37 views
+50

Density of primes in a polynomial

Consider that p(x) is a polynomial with integer coeficients. What is the natural density of the below set? $$A = \{n\ |\ p(n)\ is\ prime\}$$ and can we say an statement like prime number theorem ...
1
vote
1answer
36 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 ...
5
votes
2answers
345 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
43 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
28 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
201 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$.
5
votes
2answers
299 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 ...
3
votes
2answers
112 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
48 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
9answers
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
42 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
171 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
266 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
58 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
83 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
16 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 ...
14
votes
2answers
285 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
348 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 ...
3
votes
1answer
41 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 ...
5
votes
1answer
76 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
62 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
286 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 ...
1
vote
2answers
246 views

“Quadly” numbers with just 4 factors

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008) My method of attacking this problem started ...
3
votes
2answers
878 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
30 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 ...
-1
votes
1answer
51 views

On no. of solutions of product of positive integers equal to sum [on hold]

$n \ge 2$ be an integer , let $a(n)$ be the no. of solutions in positive integers of $x_1+x_2+...+x_n=x_1x_2...x_n ; x_1 \le x_2 \le ... \le x_n$ , then is it true that $a(n+1)=1 \implies n$ is ...
1
vote
0answers
37 views

Do you know any answer for equation y^2 = x^3 + k? [duplicate]

As you know, the equation y^2 = x^3 + k for k like (4n-1)^3 - 4m^2 that m , n are integers & no prime number that p is congruent to 1 modulo 4 count m, don't have any answer & it's proof is by ...
3
votes
2answers
174 views

A natural number $n>2$ is a prime iff $\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}$

Is this proof acceptable ? Theorem 1 (Wilson). A natural number $n>1$ is a prime iff: $$(n-1)! \equiv -1 \pmod n.$$ Theorem 2. A natural number $n>2$ is a prime iff: ...
4
votes
3answers
137 views

Interesting behavior of $\frac{n}{v_2(n!)+1}$.

I've lately noticed some interesting behavior from the values of the function $f(n)=\frac{n}{v_2(n!)+1}$, Where $v_p(n)$ is the $p$-adic valuation of $n$, and we also know that ...
0
votes
0answers
118 views

Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by: $$ \ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1. $$ For all terms of $A$ greater than $\ ...
2
votes
1answer
98 views

Infinite families of prime numbers

What interesting/useful infinite families of prime numbers are there? Right now it would be useful if I could find one with arbitrarily many 1's in its binary representation, but I am doing a larger ...
8
votes
2answers
298 views

Is $7^{8}+8^{9}+9^{7}+1$ a prime? (no computer usage allowed)

Prove or disprove that $$7^{8}+8^{9}+9^{7}+1$$ is a prime number, without using a computer. I tried to transform $n^{n+1}+(n+1)^{n+2}+(n+2)^{n}+1$, unsuccessfully, no useful conclusion.
3
votes
3answers
76 views

Prove that there exists $s$ such that $s(ab-1)^n +1$ is composite

I find this interesting question in a number theory book. Given two positive integers $a, b$ such that $a>1, b>1, \gcd(a, b)=1$. Prove that there exists a positive integer $s$ such that ...
3
votes
4answers
120 views

Prove that $2^{10}+5^{12}$ is composite

Prove that $2^{10}+5^{12}$ is composite I need to solve this using only high school mathematics. Any ideas?
4
votes
2answers
52 views

$(n+1)^{\textrm{st}}$ prime less than $2^{2^n}$

Using elementary means, show that the $(n+1)^{\textrm{st}}$ prime is less than $2^{2^n}$ please do not use fancier stuff like the prime number theorem or beyond. using this how can you show that ...
2
votes
3answers
42 views

Prove that for any natural number $n$ there exists a prime number $p$ greater than $n$

Prove that for any natural number n there exists a natural prime number p , such that $ p>n $. How can I prove that ? Thank you.