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

15
votes
3answers
1k views

Use this sequence to prove that there are infinitely many prime numbers. [duplicate]

Problem: By considering this sequence of numbers $$2^1 + 1,\:\: 2^2 + 1,\:\: 2^4 + 1,\:\: 2^8 +1,\:\: 2^{16} +1,\:\: 2^{32}+1,\ldots$$ prove that there are infinitely many prime ...
0
votes
1answer
48 views

If $b^3\mid c^2\qquad c,b\in \mathbb N$ prove that $b\mid c$

If $b^3\mid c^2\qquad c,b\in \mathbb N$ prove that $b\mid c$ What I did: $b=p_1^{\alpha 1}\cdot p_2^{\alpha 2}\cdot \dots \cdot p_k^{\alpha k}$ $c=p_i^{\beta 1}\cdot p_{i+1}^{\beta 2}\cdot ...
4
votes
0answers
83 views

Effect of 'Prime conspiracy' on the fact that prime numbers are the generators of integers [closed]

In Unexpected biases in the distribution of consecutive primes, the authors have discovered that prime numbers have decided preferences about the final digits of the primes that immediately follow ...
2
votes
1answer
68 views

Consecutive prime numbers multiplication pattern

Playing with primes in excel I came to a pattern that I do not understand and I would like to know more about it. Example: |Prime numbers | Multiplies | Subtraction of | Difference of | ...
-1
votes
0answers
51 views

Whose theorem is this?

Theorem. If $x$ is composite, it has two factors $k,a$ such that $x=ka$ and $x\gt k\ge a$. If $k$ is the greatest factor of $x$, $a$ is prime. Proof. $k$ is the greatest factor of $x$, so $a$ is ...
1
vote
0answers
29 views

Why does $\equiv 1\ (\text{mod}\ n)$ seem so important?

I'm not great with math so please feel free to correct any mistakes in my question (or add more examples). I'm a software engineer and have recently wanted to better understand the maths behind RSA ...
4
votes
2answers
98 views

Unable to find solution for $a^2+b^2-ab$, given $a^2+b^2-ab$ is a prime number of form $3x+1$

I have a list of prime numbers which can be expressed in the form of $3x+1$. One such prime of form $3x+1$ satisfies the expression: $a^2+b^2-ab$. Now I am having list of prime numbers of form $3x+1$ ...
1
vote
0answers
32 views

Constructing a smooth function whose roots consist only of each of the primes.

My first attempt: $$f(x) = \prod_{i=1}^\infty \left(1- \frac x {p_i} \right)$$ If we take a look at the Riemann zeta function: $$ \zeta(s) = \sum_{n = 1}^\infty \frac 1 {n^s} = \prod_{i = 0}^\infty ...
6
votes
1answer
109 views

Proportion of elements of prime order $p$ in $S_n$

I was trying to answer the following question recently : What is the proportion of elements of order $p$ in the symmetric group $S_n$ , where $p$ is some prime number ? I managed to work out that in ...
1
vote
0answers
23 views

Let $m =\prod_{i=1}^{r} p_i^{α_i}$, with $α_i \ge 1$ and $p_i \ge 3$ for each $i$, be the canonical representation of $m$ and…

Let $m =\prod_{i=1}^{r} p_i^{α_i},$ with $α_i \ge 1$ and $p_i \ge 3$ for each $i$, be the canonical representation of $m$ and let $a$ be relatively prime to $m$. Show that $x^2 \equiv a \pmod m$ is ...
2
votes
1answer
35 views

Bound for Chebyshev function

Consider the Chebyshev function defined as: $\psi(x)=\sum\limits_{n\leq x} \Lambda(n)$, where $\Lambda(n)=\log p$ if $n$ is a power of some prime $p$ and is equal to $0$ otherwise. Could someone ...
1
vote
2answers
46 views

Notation without cases? $f(x)=\begin{cases}p,&\text{if $x=p^k$}\\1,&\text{otherwise}\end{cases}$

Is there any other way to write the function $f:\Bbb N\to\Bbb N$ such that $$f(x)=\begin{cases}p,&\text{if $x=p^k$}\\1,&\text{otherwise}\end{cases}$$ when $p$ is prime and $k\in\Bbb N$?
3
votes
2answers
180 views

Is $1000000000000066600000000000001$ (Belphegor's prime) actually a prime?

There is a Wikipedia article about that evil Belphegor's prime, but the references there seem relatively weak. Is this number actually a prime?
1
vote
3answers
159 views

How to prove the number is a prime?

A natural number $n$ has the property that if $d$ divides $n$ then $d+1$ divides $n+1$. Show that $n$ must be a prime.
1
vote
1answer
48 views

What's about $\sum_{k=1}^{n-1} p_{k} \sum_{l=k+1}^{n} p_{l}$ for prime numbers?

By specialization of this formula, here in PROBLEMA 36, page 453 (in spanish), taking $\frac{1}{x_i}$ as the ith prime number we've (with at least two summands) $$ \left( \sum_{k=1}^{n} p_{k} ...
1
vote
0answers
35 views

Primes congruent to {0,2} modulo 3 and the greatest common divisor of $2s(s-1)$

This problem is related to the question asked here: The primes $s$ of the form $6m+1$ and the greatest common divisor of $2s(s-1)$ I would like to prove the following. If $s$ is prime Let $\psi(s) = ...
1
vote
2answers
25 views

Can the product of two Fermat witnesses where the witnesses are prime be a Fermat liar?

Let $n$ be composite. If $a$ is coprime to $n$ such that $a^{n-1} \equiv 1 \pmod n$ then $a$ is called a Fermat liar. If $a^{n-1} \not\equiv 1 \pmod n$, then $a$ is a Fermat witness to the ...
1
vote
0answers
22 views

On a theorem of Hensel

In the paper Binomial coefficients modulo prime powers, Andrew Granville state the following theorem: Let $n, m$ and $r=n-m$ be three given positive integer and $p^k$ is the exact power of $p$ ...
1
vote
0answers
46 views

Sum of first n primes [duplicate]

Can we claim it is asymptotic to $n^2\log n$? I argue that because $p_n\sim n\log n$, we can say: $$\sum_n n\log n=\log1+2\log2+\dots+n\log n$$ $$=\log1+\log2+\dots+\log n$$ $$+\log2+\dots+\log n$$ ...
4
votes
0answers
22 views

What is known about the counting function of Gaussian primes"

The counting function of primes among $\Bbb{N}$, describing the asymptotic density of the primes, is well known (the Prime Number theorem). Let's define a mild generalization of the counting function ...
27
votes
7answers
3k views

Can a complex number be prime?

I've been pondering over this question since a very long time. If a complex number can be prime then which parts of the complex number needs to be prime for the whole complex number to be prime.
4
votes
1answer
440 views

If more than one prime number satisfies a given congruence, must an infinite number of primes satisfy that congruence?

I understand that this is kind of a broad question, but if no affirmative proof is known, can anyone give a counterexample?
0
votes
1answer
31 views

What are the solutions to this equation (primes, modular arithmetic)?

Given: $m,n\in\mathbb{N}$ and $p$ is prime. Find the solutions to the following equation: $$m^2-3mn+(np)^2=12p$$ Thank you in advance.
2
votes
4answers
127 views

For every positive integer $n$, $n^2 + n +19$ is prime

I'm trying to prove that for every positive integer $n, n^2 + n +19$ is prime. I tried to disapprove it saying that is is not prime. If it's not prime, then $n^2 + n +19$ has to have at least two ...
1
vote
1answer
87 views

Possible divisors of $s(2s+1)$ follow up question.

This question is related to this post:Possible divisors of $s(2s+1)$. I have some follow up questions which should be a new post. I write $\psi(s) = s(2s+1)$. We showed that for every prime $s$ that ...
2
votes
1answer
98 views

Largest prime gap under $2^{64}$

Thanks to Tomás Oliveira e Silva's extensive calculations, it is known that the largest prime gap less than $4\cdot10^{18}\approx2^{61.8}$ is 1476. I'd like an upper bound for the largest prime gap ...
1
vote
0answers
37 views

Distribution of final digits of consecutive primes

There's been a lot in the press recently about the unexpected distribution of final digits in pairs of consecutive primes, and many people have written programs to confirm the observation that pairs ...
1
vote
0answers
18 views

Primes from the given set

If we are given a set of positive integers and asked to find the prime numbers from this set considering the divisor must belong to this set only, Is there any way apart from dividing every number ...
0
votes
1answer
61 views

Prove that for any prime $p$ there exist natural numbers $a,b$ for which $ p$ divides $a^2+b^2+1$ [closed]

Prove that for each prime $p$ there exist natural numbers $a,b$ for which $p$ divides $a^2+b^2+1$
1
vote
1answer
20 views

Let p be an odd prime with $(a,p) = 1$ and $(\frac{a}{p})$ = 1. show that $x^2$ ≡ a (mod p)

Let p be an odd prime with $(a,p) = 1$ and $(\frac{a}{p})$ = 1. show that $x^2$ ≡ a (mod p) has precisely two incongruent solutions mod p. Having a bit of trouble with this question, we are ...
2
votes
3answers
56 views

The primes $s$ of the form $6m+1$ and the greatest common divisor of $2s(s-1)$

I had trouble coming up with a good title. Let $\psi(s) = 2s(s-1)$. I write $(\psi(s),\psi(s+2))$ to be the greatest common divisor of $\psi(s)$ and $\psi(s+2)$. Then if $s$ is prime and ...
2
votes
2answers
49 views

Possible divisors of $s(2s+1)$

I write $\psi(s) = s(2s+1)$ and let $d$ be the divisor function. If $s$ is prime then 4 divides $d(\psi(s))$. For example if $s=37$ then $d(\psi(s)) = d(2775) = 12$ and $4|12$. Is this trivial? I am ...
1
vote
0answers
36 views

Is it possible to show that there are integer solutions $n,m$ for $10^m+10^n+1\equiv 0$ (mod $q$) for a prime $q$?

I came across to this question: Prime numbers are related by $q=2p+1$ I have almost figured out the answer, but got stuck at the final step to show the following: For prime numbers $p,q$ that ...
2
votes
0answers
23 views
1
vote
0answers
63 views

What is the limit inferior of $p_n^2/ (\log p_n) \left\lvert 1-e^\gamma\log(p_n+\log^2p_n+\varepsilon_n)\prod_1^n (1-1/p_k)\right\rvert$?

Let $p_n$ be the $n$-th prime number. The $\varepsilon_n:=\varepsilon(p_n)$ in the title is an infinitesimal sequence chosen so that, replacing $p_n$ with $x$, we have$$\lim_{x\to+\infty} ...
4
votes
1answer
66 views

Lower bound on $\pi(x)$

The book I am working through uses the bound $\pi(x)>\frac{x}{ \log x}$ without proof. Is it possible to prove this in a simple way using Sieve methods?
0
votes
2answers
43 views

Representations of some primes as $3x^2-4y^2$?

I am looking for (elementary) proofs (idea of the proofs is also OK) or references to proofs of the followings: $$ p\equiv11\pmod{12}\longrightarrow p=3x^2-4y^2 $$ Any help appreciated.
3
votes
3answers
736 views

Proof involving twin primes

I have to prove that if $p$ and $p+2$ are twin primes, $p>3$, then $6\ |\ (p+1)$. I figure that any prime number greater than 3 is odd, and therefore $p+1$ is definitely even, therefore $2\ |\ ...
1
vote
2answers
943 views

Is it something new?

$W(n)$ is the function that counts number of distinct prime divisors of $n$. I have been able to prove for any $m$ consecutive integers starting with $1+a$ with the condition $a\leq (m^2-4m)/4$ , ...
1
vote
2answers
50 views

Twin Prime Related Material

I'm in a senior seminar class for my undergraduate degree and I am tasked with writing a short, 12 page paper on some subject I have not been taught before. I chose the twin prime conjecture. My ...
1
vote
1answer
124 views

S.S. Pillai on Consecutive integers research paper?

I am trying to prove: Given any seventeen consecutive integers, there does not exist one which is coprime to the rest. I am aware S.S.Pillai proved a similar statement for $m$ consecutive ...
-2
votes
1answer
45 views

Let $a_1 = 2$ and for all natural number n, define $a_{n+1}= a_{n}(a_{n}+1)$. Then as $n\rightarrow \infty$, the number of prime factors of $a_{n}$ [closed]

Let $a_1 = 2$ and for all natural number n, define $a_{n+1}= a_{n}(a_{n}+1)$. Then as $n\rightarrow \infty$, the number of prime factors of $a_{n}$: goes to infinity. goes to a finite limit. ...
0
votes
1answer
33 views

Geometry: Determining the length of a side of a triangle [closed]

Triangle $ABC$ has all sides of integral length. Vertex $A$ is at $(0,0)$, $B$ lies on the line joining $(0,0)$ and $(3,6)$ and $C$ lies on the line joining $(0,0)$ and $(2,-1)$. Two of the three ...
59
votes
3answers
1k views

Mathematicians shocked(?) to find pattern in prime numbers

There is an interesting recent article "Mathematicians shocked to find pattern in "random" prime numbers" in New Scientist. (Don't you love math titles in the popular press? Compare to the source ...
0
votes
1answer
32 views

Representations of some primes as $x^2-2y^2$?

I am looking for (elementary) proofs (idea of the proofs is also OK) or references to proofs of the followings: $$ p\equiv\pm1(\mod8)\longrightarrow p=x^2-2y^2 $$ Any help appreciated.
0
votes
4answers
57 views

Show that $a_{n+1}$ and $a_{n}$ are relatively prime for all $n$

I would appreciate if somebody could help me with the following problem: Show that $a_{n+1}$ and $a_{n}$ are relatively prime for all $n$ where $$a_{n+2}=2a_{n+1}+a_n, a_1=1, a_2=2$$
4
votes
2answers
104 views

Perfect Square Arising from Prime Pythagorean Triple

This problem appears as the second question in the British Mathematical Olympiad 2014--2015 Round 1 paper (https://bmos.ukmt.org.uk/home/bmo1-2015.pdf). Positive integers $p$, $a$ and $b$ satisfy the ...
2
votes
0answers
31 views
1
vote
0answers
44 views

Functional equation on integers: $f(m\cdot n)=f(m)f(n)$ and $f(m+n)=f(m)+f(n)$

Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $f(m \cdot n) = f(m) f(n)$ for $\gcd(m, n) = 1$ and $f(m + n) = f(m) + f(n)$ for $\forall m, n \in \mathbb{P}$. I think only ...
1
vote
0answers
11 views

Suppose that $n$ is a composite, squarefree integer such that for every prime divisor $p$ of $n$… [duplicate]

Suppose that $n$ is a composite, squarefree integer such that for every prime divisor $p$ of $n$, we have $(p - 1) | (n - 1)$. Prove that $n$ is a Carmichael number. Having a lot of trouble with this ...