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

3
votes
1answer
30 views

Would this sequence (OEIS A068374) be somehow attached to the twin prime conjecture?

Today I came across an interesting sequence at OEIS, A068374, described as "Primes $n$ such that positive values of $n$-Primorial($k$) are all primes ($k\gt0$)". The sequence is as follows: $(2, ...
9
votes
2answers
92 views

Prove there are infinitely many primes in $\mathbb{Z}[i]$

I saw a proof online there are infinitely many primes in $\mathbb{Z}$. The Euler product let's us factor the harmonic series: $$ \prod \left( 1 - \frac{1}{p} \right) = \sum \frac{1}{n}$$ I wonder ...
2
votes
1answer
62 views

Can the prime $619$ ever be the least prime factor 0f f(n)?

Let f(n)=$1234567891011$...n (i.e. concatenating the first n integers). And consider this sequence of numbers n: n=2 is the first case where 2 is the least prime factor of f(n) n=3 is the first ...
1
vote
2answers
35 views

Prove that for all primes p: $φ(p^i)$= $p^i$ - $p^{i-1}$

Prove that for all primes p: $φ(p^i)$= $p^i$ - $p^{i-1}$ I found a proof on the wikipedia article of the Euler's totient function. But I cannot understand it, as it's been many years since I dealed ...
4
votes
1answer
68 views

Proving $\lim_{n \to \infty} \frac {\log{p_n}} {\log n} = 1$

How do I show: $$\lim_{n \to \infty} \frac {\log{p_n}} {\log n} = 1$$ where $p_n$ is the $n$th prime number without using the Prime Number Theorem? Some context: The reason I can not use the PNT ...
0
votes
1answer
23 views

Davenport Reference for Prime Number Theorem

On page 40 in Harold Davenport's book "The Higher Arithmetic" he gives a reference in section 10 for an elementary proof of the prime number theorem as "Math. reviews, 10 (1949), 595-6" but I can't ...
-4
votes
2answers
71 views

How can I prove or disprove that the formula $2^{2{^{2^{2^2\dots}}}}+1$ gives a prime number? [duplicate]

I could calculate the following $$2+1=3$$ $$2^2+1=5$$ $$2^{2^2}+1=17$$ $$2^{2{^{2^2}}}+1=65537$$ Now how can I prove or disprove the formula always gives a prime number
1
vote
1answer
35 views

if ka + lb = 1, then a and b are relatively prime

Me and a friend are having a small arguement. My friend says the statement is false but I'm saying its true. My friend thinks its false because ka + lb does not necessarily equal 1. Rather, it can ...
1
vote
0answers
42 views

Prove this inequality for sufficiently large $n$

Prove that the above inequality holds for sufficiently large $n$: $$\pi(2n) - \frac{3}{2} \pi(n) \ge O\left(\frac{\ln n}{(\ln \ln n )^2}\right)$$ $\ln n$ denotes to natural logarithm and $\pi(n)$ is ...
1
vote
1answer
50 views

GCD of a special class of numbers

Let $b, n \geq 2$. Is is true that the GCD of all the numbers $(b^n-1)/(b^d-1)$, where $d$ runs over all the proper positive divisors of $n$ (i.e., $d < n$ and $d \mid n$), strictly exceeds $1$? I ...
6
votes
1answer
126 views

Is $\sum_{p}\frac{1}{p^{2}}$ irrational?

Is $\sum_\limits{p}^{\infty}\frac{1}{p^{2}}$ irrational where p is prime? How to prove it?
0
votes
1answer
6 views

How to return back element in Zp using pow?

For example I have value 2 2**17 % 31 = 4 4**23 % 31 = 2 And return value 2 What is the name of that equation, and how to find pairs like (17,23) over mod 31 ? ...
1
vote
3answers
42 views

Constructing a bijection from $\mathbb{N}$ to $\mathbb{Z}$ using primes and composites?

Reviewing for an Into to Proofs final, came across the classic $f:\mathbb{N} \to \mathbb{Z}$ bijection problem in which $f(x) = \begin{cases} \displaystyle \frac{x}{2} &\mbox{if $x$ is ...
1
vote
0answers
37 views

Is there a closed form for $\sum_p 1/2^p$?

Consider the sum $\sum_p {1 \over 2^p}$, where $p$ is the prime numbers. It obviously converges, because $\sum_{\Bbb N} {1 \over 2^n} = 1$, so that's an upperbound. And in fact this sum is ...
0
votes
0answers
17 views

Gauss lemma-proof clarification

I've found proof of Gauss' Lemma: The product of primitive polynomials is primitive in "The Carus Mathematical Monographs. The theory of algebraic numbers, 1975" as follows: Let $a_0+a_1x+...+a_nx^n ...
2
votes
0answers
38 views

Linear convex combinations of $Li(x)=\int_2^x\frac{1}{\log(t)}dt$ and $\frac{x}{\log(x)}$, and prime counting function

Can provide us a linear convex combination of $Li(x)=\int_2^x\frac{1}{\log(t)}dt$ and $\frac{x}{\log(x)}$ a better approximation for $\pi(x)$, the prime counting function? Or not, is better $Li(x)$ ...
2
votes
1answer
68 views

When is the first case where $67$ is the least prime factor of f(n)?

Let f(n)=$1234567891011$....n (concatenation of first n natural numbers). I make a sequence of numbers made with this following definition: Smallest number n such that the m-th prime number is the ...
1
vote
2answers
101 views

Is there a well known nontrivial counterexample to this claim?

Suppose we have $A\subseteq\mathbb{N}$ with the property that if $B\subseteq\mathbb{N}$ and $B$ is finite, then $\exists a\in A\setminus\{ 1\}$, $\forall b\in B$, $\gcd(a,b)=1$. Are there any well ...
2
votes
5answers
68 views

Find the value of $abc$.

The product of two $3$-digit numbers with digits $abc$, and $cba$ is $396396$, where $a > c$. Find the value of $abc$. In order to solve this, should I just find the prime factorization of ...
2
votes
0answers
36 views

Do we have more primes of the form $3k+1$ or of the form $3k+2$?

Let us denote by $a_{1}(n)$ the number of prime numbers in the set $\{1,2,...,n\}$ which are of the form $3k+1$. Let us denote by $a_2(n)$ the number of prime numbers in the set $\{1,2,...,n\}$ which ...
2
votes
1answer
51 views

Number Theory: If $d\mid(4^n+1)$, show that $d$ is a sum of two squares

I have a proof for the following problem, but I'm not sure if it's correct: If $d\mid(4^n+1)$, show that $d$ is a sum of two squares. Proof $d\mid(4^n+1)\implies dm=4^n+1$, some $m\in\mathbb{Z}$. ...
3
votes
1answer
46 views

How to prove that at least one solution to $x^2 + y^2 \equiv -1 \pmod p$ exists?

How can I show this? For every prime number, $p$, there is at least one solution $(x, y)$ such that $x^2 + y^2 \equiv -1 \pmod p$. Thanks.
5
votes
1answer
54 views

prove $(n)$ prime ideal of $\mathbb{Z}$ iff $n$ is prime or zero

prove $(n)$ prime ideal of $\mathbb{Z}$ iff $n$ is prime or zero Defintions Def of prime Ideal (n) $$ ab\in (n) \implies a\in(n) \vee b\in(n) $$ Def 1] integer n is prime if $n \neq 0,\pm 1 $ ...
4
votes
1answer
59 views

$p=k n+1$ prime

This is a part of the question from CLRS (Introduction to Algorithms) Chapter on FFT and Polynomials. I am self reading and am stuck at this part. Let $n$ be a power of 2. Suppose that we search for ...
3
votes
4answers
59 views

Number Theory: Find all incongruent solutions of $x^8\equiv3\pmod{13}$.

Find all incongruent solutions of $x^8\equiv3\pmod{13}$. I know that $2$ is a primitive root of $13$ and that $2^4\equiv3\pmod{13}$, so we want to solve $x^8\equiv2^4\pmod{13}$. Now, ...
4
votes
3answers
50 views

Number Theory: Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution.

I have this problem that I'm a bit stuck on: Find $m\equiv 1\pmod4$ so that $x^2\equiv -1\pmod{m}$ has no solution in $\mathbb{Z}$. So far, I know that $m$ can't be prime because $(\frac{-1}{p})=1$, ...
2
votes
2answers
75 views

Miller-Rabin primality test for $2^{32}+1$

How can I prove that $2^{32}+1$ is composite number using Miller-Rabin primality test? I can't find a solution which verify the hypothesis of theorem.
0
votes
1answer
44 views

To prove that a sum of powers is composite?

How to prove that $5^{20} + 2^{14}$ is the composite number?
2
votes
2answers
50 views

How to write $n^4+4$ in difference if two squares format?

I have to prove that for every $n>1$, $n^4+4$ gives a non prime number and I thought that I'll have to write it in difference of two squares format. What are the steps to do that and how is its ...
2
votes
1answer
40 views

Is the diophantine equation $a = x^p - y^p$ sufficient to find $x$ and $y$ in terms of $a$ and $p$?

Let there be a natural number $a,$ that can be expressed as $a = x^p - y^p$ where $x, y$ and $p$ are natural numbers, each two of them being pairwise co-prime and $p$ is an odd prime. Then can $x$ and ...
9
votes
1answer
168 views

$p$-Splittable Integers

Let $p$ be a positive integer. For each nonnegative integer $k$, write $[k]$ for the set $\{0,1,2,\ldots,k\}$. Also, we define $[-1]:=\emptyset$. We say that an integer $k\geq -1$ is ...
1
vote
1answer
38 views

Among any $2n$ consecutive integers below $n^2+2n$ at least one has no prime divisor less than $n$?

What is your idea about my conjecture? Consider a sequence of $2n$ consecutive natural numbers, all the terms less than $n^2 + 2 n$. Then there exists at least one number in the sequence which is ...
12
votes
1answer
136 views

Conjecture about natural number satisfying $ m(n)^k+1\space\mid\space n^{2k}+1 $

Let $m(n)$ be the greatest proper divisor of $n$. Is there any number $n≥2$ not of the form $p$ or $p^3$ for $p$ prime that satisfies $$ m(n)^k+1\space\mid\space n^{2k}+1 $$ for all natural numbers ...
4
votes
1answer
98 views

Generalization on older SE question: not just covering $1$, but all rational numbers.

Older SE question lies here. So I will change the question such that you can understand the question better: $$\sum_{c\space\subset \Bbb{Co}}\frac{1}{c}\le k$$ -where your goal is to get to $k$ ...
5
votes
3answers
118 views

Proof that multiplication of two numbers plus $2$ is a prime number

Let's say we have odd prime numbers $3,5,7,11,13, \dots $ in ascending order $(p_1,p_2,p_3,\dots)$. Prove that this sentence is true or false : For every $i$, $$p_i p_{i+1}+2$$ is a prime number. ...
2
votes
2answers
70 views

Prime numbers of form $a^n-1$. [duplicate]

Let $a$ and $n$ be integers greater than $1$. Suppose that $a^n - 1$ is prime. Show that $a=2$ and $n$ is prime.
1
vote
0answers
56 views

Prove $3 \cdot 5 \cdot 7 \cdot 11 \cdot prime_n = 2k + 1$ [duplicate]

It is known that any prime greater than 2 is odd. How do I show the combinations of all primes greater than 2 is also odd, $2k+1$? I tried using induction, but what is appropriate for $prime_n$? ...
1
vote
1answer
23 views

multiplication of consecutive prime numbers in the form $4k +3$

How can I prove that prime numbers beginning with $2$, multiplied with the next consecutive prime plus $1$, $2\times3\times5\times7\times\cdots+1$, will give the form $4K+3$?
0
votes
2answers
19 views

Is this easy to prove? $\forall N, k \gt 0$, $\pi(x) - \pi(N) \gt \frac{x-N}{2k}$ for all sufficiently large $x$.

Let $\pi(x)$ be the prime counting function. Knowing that $\pi(x) \sim \dfrac{x}{\ln x}$. How could you prove that $\pi(x) - \pi(N) \gt \dfrac{x - N}{2k}$ for all $x \geq $ some $X_0$? I think ...
7
votes
2answers
73 views

Is $(3^p-1)/2$ always squarefree?

I have little conjecture. Maybe it's stupid i don't know. Let $p>5$ be a prime number. Then $(3^p-1)/2$ is always squarefree? It's true for $p<192$.(I used Mathematica.)
0
votes
1answer
36 views

I need help in solving this proof when $p_1$, $p_2, \dotsc, p_n$ are distinct prime numbers [duplicate]

So I was working on one of the exercise question for school and I came across this question and I wanted to know if someone can help me in providing a proof for this question. So the question is: ...
3
votes
1answer
136 views

Uniquely identify any finite subset of an infinite set

Let $U$ be an unbounded subset of $\mathbb{N}$. Let $D = \mathcal{P}_{<\omega}(U)$ (the set of all finite subsets of $U$). Let $f$ be an injection such that: $f: D \rightarrow \mathbb{N} $ ...
5
votes
2answers
89 views

Prove $2^p + 3^p$ cannot be a perfect power

The question: if $p$ is a prime, prove that $2^p + 3^p$ cannot be a perfect power. So far my progress is limited to noting that: 5 always divides $2^p + 3^p$, so it must divide $k$ if $k^n$ is the ...
1
vote
1answer
31 views

show that $(a+b)^{p^n}\equiv a^{p^n} + b^{p^n}\pmod p$ where $p$ is a prime and n$\ge$1.

I need to show that $(a+b)^{p^n}\equiv a^{p^n} + b^{p^n}\pmod p$ where $p$ is a prime and n$\ge$1. I came up with the following: $a^{p^n} + b^{p^n}\equiv a+b\pmod p$ But I don't know if I can use ...
1
vote
0answers
130 views

Is there a proven way to calculate the entry point(first occurence) of a factor m, in the Fibonacci sequence?

I saw a comment at the OEIS website for the sequence of entry points, of Fibonacci factors. https://oeis.org/A001177 It referenced a paper by Mark Renault in 1996, with the quote from OEIS: ...
0
votes
1answer
18 views

Show that $P$ contains a subgroup of ordre $p^t$ - Use Cauchy's Theorem and the proposition $7.2$

Let $P$ a group of order $p^s$ ($p$ is prime) and $t \leq s$. Use Cauchy's Theorem and the proposition $7.2$ for showing P contains a subgroup of order $p^t$. Cauchy theorem : (1) Let $G$ a ...
4
votes
3answers
141 views

How to prove $\sum_p p^{-2} < \frac{1}{2}$?

I am trying to prove $\sum_p p^{-2} < \frac{1}{2}$, where $p$ ranges over all primes. I think this should be doable by elementary methods but a proof evades me. Questions already asked here (eg. ...
1
vote
0answers
25 views

On the distribution of the primes / the probability of a false positive from Miller-Rabin

This is my second question today about Miller-Rabin; this should be it for a while :). Assume we're using Miller-Rabin to test whether $n$ is prime. Let $T_k$ be the event that $n$ passes $k$ rounds ...
6
votes
1answer
61 views

Why does A005179 (smallest number with N factors) have spikes at prime numbers of factors?

A005179 is a list of the lowest number with n factors, for each n. The list has rather extreme local maxima when n is prime. Why? ...
3
votes
2answers
75 views

Is the concatenation of all prime numbers, a universe number?

A universe number is a number which contain any finite lengh string of digits for a base. Reference here. Then the question is, is the concatenation of all prime numbers, a universe number? ...