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
2answers
47 views

On primality of the numbers of the form $10^{2k} - 10^{(k+1)} -1$

Has anyone seen proof that numbers of the form $10^{2k} - 10^{k+1} - 1 \space \forall k \ge 2$ are prime?
6
votes
0answers
134 views

Is there a quicker way to generate integers which are hard to factor than multiplying two large primes?

An easy way to generate an integer which is hard to factor is to find two large primes and multiply them. As a bonus, you know the factors. I'm interested in whether it's possible to find integers ...
0
votes
1answer
140 views

Is this statement equivalent to Goldbach's conjecture

Given a number $n\ge 3$, then one of these is true: \begin{equation} \begin{cases}2n = (6m-1)+P, \ \ \ P \in \mathbb P, \ 6m-1 \in \mathbb P, \ 6m+1 \in \mathbb P \ \ \ \ (1) \\ 2n-1 \in \mathbb P, \ ...
3
votes
3answers
69 views

Number of primes from $n!+1$ to $n!+n$

Why aren't there any primes between $n!+1$ and $n!+n$ for all $n>1$? This question was on AHSME 1969 #23, but the question is trivial because it's multiple choice. However, I have no idea how to ...
4
votes
2answers
69 views

If for almost all $p \equiv 1$ (mod a) it holds that $p \equiv 1$ (mod m), then…

Let $a,m\in \mathbb N$ Suppose that for almost all primes $p \equiv 1$ (mod a) we have that $p \equiv 1$ (mod m) Can we say something about $a$ and $m$? For example $m$ divides $a$ or vice versa? I ...
2
votes
3answers
304 views

Statistical observations about primes

Are there statistical observations about prime numbers showing that primes are not random? For example obviously primes are $1$ or $-1$ mod $6$, but are these remainder distributed equally? What I ...
25
votes
5answers
16k views

Is there a known mathematical equation to find the nth prime?

I've solved for it making a computer program, but was wondering there was a mathematical equation that you could use to solve for the nth prime?
3
votes
2answers
34 views

Is it known whether there are ever infinitely many primes of the form $\prod_i p_i^{n_i} + 1$ where the $p_i$ are fixed primes but the $n_i$ can vary?

So if we fix finitely many primes $p_i$, where one $p_i$ is $2$, but let the powers $n_i$ on the $p_i$ vary, is it known whether it is ever possible to have infinitely many primes of the form $\prod_i ...
2
votes
1answer
48 views

Comparing $\pi(x)$ and $\pi^{(k)}(x)$

We say a k-almost prime is an integer that results as the product of k prime, counting repetition. For example, $12$ is a $3$-almost prime as $12= 3 \times 2 \times 2$. Additionally, we define ...
0
votes
0answers
9 views

Convenient goedel numbering for finite register machines?

Overview I'm trying to find a goedel numbering for finite register machines, which is convenient in two ways: when ordering machines by their numbering, simple machines shall come first, i.e. ...
2
votes
1answer
71 views

How do computers generate primes so quickly?

From what I understand, when a computer encrypts a file using an encryption standard like RSA, one of the steps is to generate two large primes, and multiply them together. I have created RSA keys on ...
-2
votes
0answers
33 views

Primes with a very special form [duplicate]

This question is related to the power cyclic and congruences. Does there exist a prime of the form 2^3^5^7^11^13^....^p(n-1)^p(n)+ p(n)^p(n-1)^p(n-2)^....^11^7^5^3^2 where p(n) is the n-th prime ...
7
votes
2answers
178 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
0
votes
1answer
43 views

Time complexity of a simple factoring algorithm?

This has puzzled me for a little. I start off with a list of primes that is sufficiently large. For my number $n$, I do trial division of primes in ascending order until I reach a prime that divides ...
1
vote
2answers
21 views

Distribution of decimal repunit primes

The prime number theorem describes the distribution of prime numbers in positive integers. Is there a similar theorem describing the distribution of primes among positive integers of the form ...
0
votes
1answer
24 views

Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n

Given the number $n=35$.Find all numbes $1\le a\le n-1$ which are prime to n and they are not witness Fermat of compositeness of n I found this problem on internet and i am trying to find a solution ...
5
votes
1answer
88 views

Finding Gaussian Primes along Lines in $\mathbb Z[i]$

I am trying to prove the following statement: For all positive integers $a$ does there exists a positive integer $b$ such that $a^2 + b^2$ is prime? (If so, can we provide such a $b$?) Given the ...
0
votes
1answer
73 views

Using The Riemann Zeta Functional Equation

Riemann was able to establish the following link between the Riemann zeta function and the weighted prime counting function $J(x)$. $$\ln(\zeta(s))=s\int_1^\infty J(x)x^{-s-1}dx$$ Using the Mellin ...
1
vote
0answers
43 views

Probability number is divisible by half the square of a prime?

Let $p$ be a prime. What is the probability that a number of the form $\left \lceil \frac{p^2}{2} \right \rceil$ divides a random positive integer $n$. I have a solution that involves the Riemann-Zeta ...
7
votes
1answer
99 views

Distribution of the sum reciprocal of primes $\le 1$

$$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\cdots \le 1 $$ This is an interesting infinite summation. This is very closely resembling my other problem with has to do with the distribution of ...
5
votes
5answers
96 views

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5

what is the greatest integer that divides $p^4-1$ for every prime number p greater than 5(this is a gre subject math problem) I think that $p^4-1=(p^2+1)(p-1)(p+1)$,so 8 must divide all the $p^4-1$ ...
-1
votes
1answer
112 views

The asymptotic of the first Chebyshev function, using the Prime Number Theorem [closed]

Using the prime number theorem, show that: $\vartheta (x) \sim x$ Where $\vartheta (x) := \sum_{p \le x} \log p$ Any help on this would be great, thanks in advance.
3
votes
1answer
28 views

Is there a way to estimate the number of positive integers less than or equal to $n$ that have a given prime $p$ as a least prime factor

The probability that an integer $p$ divides an integer $x$ is $\dfrac{1}{p}$. From this article on almost prime numbers, the number $\pi_k(n)$ of positive integers less than or equal to $n$ with at ...
0
votes
1answer
21 views

What is the summatory function of the number of (not necessarily distinct) prime factors?

In the Math World article on Merten's Constant, a related constant $B_2$ is mentioned which "appears in the summatory function of the number of (not necessarily distinct) prime factors." I am very ...
1
vote
2answers
74 views

Do prime numbers have prime factors?

(This is a somewhat trivial question). Do prime numbers have prime factors, i.e. itself? For example is 7 a prime factor of 7? The reason I ask this is because there is a statement in my lecture ...
1
vote
2answers
45 views

Is it true that $(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1$?

Notation: $(a,b) = \gcd(a,b)$ If $p,q$ are distinct odd primes, is it true that $$(pq,(p-1)(q-1)) =1 \iff (pq,\operatorname{lcm}(p-1,q-1))=1\;?$$
2
votes
3answers
50 views

Find all numbers that have 30 factors and have 30 as one of their factors.

Find all numbers that have 30 factors and have 30 as one of their factors. Thank you. Note: please show way if possible.
1
vote
4answers
88 views

How do I show that:if$p$ is prime $>5$ then $p^4-20p^2+19$ is always divisible by $180$.?

Is there someone who can show me How do i show that :If $p$ is a prime number greater than $5$ then : $$p^4-20p^2+19$$ is always divisible by $180$. Note : i think should factor $p^4-20p^2+19=$ ...
1
vote
1answer
31 views

Find the smallest prime number that doesn't divide any 5-digit number whose digits are in strictly increasing order.

Find the smallest prime number that doesn't divide any 5-digit number whose digits are in strictly increasing order. I have posted an answer of my own below; any alternative solutions will also be ...
3
votes
2answers
51 views

How is the Twin Primes Constant useful? What value does it provide over Brun's Constant?

The Twin Primes Constant is: $$\prod_{p > 2 \text{ and a prime }}\left(1 - \frac{1}{(p-1)^2}\right) = 0.6601618158\ldots$$ It appears that in this case $p$ does not have to be a prime. But if ...
1
vote
1answer
231 views

How to get this equation solved?

I came across this equation $$\sqrt a-\sqrt b=\sqrt 7-\sqrt 5$$ And you have to find the value of '$a$' and '$b$' when both of them are primes. The solution was $a=7, b=5$. Now, my question is, ...
2
votes
0answers
29 views

Prime from mirror concatenation of first primes

The mirror concatenation of the first 1, 6 and 8 prime numbers with no primes being reversed is a prime ! i.e. 131175323571113 and 19171311753235711131719 are prime numbers! (beautiful primes!). After ...
14
votes
6answers
2k views

Prove a number is composite

How can I prove that $$n^4 + 4$$ is composite for all $n > 5$? This problem looked very simple, but I took 6 hours and ended up with nothing :(. I broke it into cases base on quotient remainder ...
2
votes
1answer
68 views

Proof that $2^n-1$ does not always generate primes when primes are plugged in for $n$?

Exactly what the name entails. The function $2^n-1$ I see largely tends to generate primes when $n$ is prime. However, a week ago I heard that this was horribly false. Please show me a disproof.
10
votes
4answers
405 views

Is there a function that can be subtracted from the sum of reciprocals of primes to make the series convergent

The gamma constant is defined by an equation where the harmonic series is subtracted by the natural logarithm: $$\gamma = \lim_{n \rightarrow \infty }\left(\sum_{k=1}^n \frac{1}{k} - \ln(n)\right)$$ ...
3
votes
3answers
81 views

Storing a natural number as a set of its Nth prime factors, how much data is used?

Spoiler, tap to reveal. In asking the following question, I knew that each natural number could be prime factorised. However I assumed that most natural numbers would each be equal to the ...
2
votes
3answers
44 views

Proving that $i! \mid (p-1)\cdot(p-2)\cdots(p-i+1)$ for $i < p$

Started solving this problem: $$ (a+b)^p \equiv a^p+b^p \pmod{p}$$ where $p\in\mathbb{P}$, $a,b\in\mathbb{Z} $ After a few implications I arrived to this $$ i! \mid ...
1
vote
1answer
470 views

Sum of three primes equal to a prime [closed]

Does anyone know how to always get a prime from the sum of three primes? For example: $5+7+11=23$, $17+29+43=89$, etc.
0
votes
3answers
162 views

A question on consecutive prime numbers

Prime numbers: $2$ $3$ $5$ $7$ $11$ $13$ $17$ $19$ $23$ $29$ .... Difference between to consecutive primes: $1$ $2$ $2$ $4$ $2$ $4$ $2$ $4$ $6$ .... We know that there are infinite prime numbers. ...
2
votes
3answers
3k views

First 10-digit prime in consecutive digits of e

Problem. What is the first $10$-digit prime in consecutive digits of $e$. For those of you who don't know, in 2004 the answer produced a URL to a Google employment page (sort of). I just found about ...
8
votes
1answer
125 views

Number made from ending digits of primes

Consider the number $0.23571379391713739171393971379371799173739113791379391173917133713717793$ ... The number is formed by the ending digits of the prime numbers. Is it known whether this number ...
9
votes
2answers
491 views

Primes dividing the values of integer polynomials

Problem: Let $n$ be an integer and $p$ a prime dividing $5(n^2-n+\frac{3}{2})^2-\frac{1}{4}$. Prove that $p \equiv 1 \pmod{10}$. The polynomial can be re-written as ...
3
votes
1answer
48 views

Inverse of prime counting function

The prime counting function $ \pi (x) \approx \dfrac {x} {\ln(x-1)} $. This function returns the number of primes less than $x$. Note: $x-1$ gives a better estimate than $x$. How to find $x$ given $ ...
1
vote
1answer
48 views

If Wieferich primes are finite…Then what?

I am wondering if $1093$ and $3511$ are the only Wieferich Primes, then what would it imply? (A wieferich prime is a prime satisfying the congruence $2^{p-1}\equiv 1\ mod \ p^2 $). I know of 3 cases; ...
0
votes
1answer
71 views

Are all even numbers the difference of prime powers

Does there exist an even positive integer greater than $100$ (to eliminate trivial cases) that cannot be expressed in the form: $p^2-q$ $p-q^2$ $p^2-q^2$ $p^3-q^3$ where $p$ and $q$ are primes.
2
votes
2answers
71 views

$\pi(x)$ Proof Clarification

In a proof from a number theory book that $${\pi(x) \over x}\le {2k \over x} + {\phi(k) \over k}$$ Where $x=kl+r$ with $0 \le r\lt k $ It is stated that $$\pi(x) \le k+(l-1)\phi(k) + r \le 2k+{x\over ...
1
vote
5answers
754 views

why only square root approach to check number is prime [closed]

Why do we use only square root approach to find a number is prime or not? why not cube root & 4rth root?
6
votes
1answer
72 views

Is $\pi(n)$ a Rational Function?

Are there some two-variable polynomials $P(n,\log n)$ and $Q(n,\log n)$ which we have the bellow equation for prime counting function $\pi(n)$ for $n \in \mathbb{n}$? $$\pi(n) = \Bigl{\lfloor} ...
4
votes
1answer
47 views

Prime Zeta Function proof help: Why are these expressions not equal?

I was trying to create a formula for the Prime Zeta function and I partially succeeded except for one frustrating error. I was only able to formulate an approximation. Consider the following sum: ...
5
votes
13answers
2k views

What are the properties of a prime number? [closed]

For instance, we know that odd numbers behave like: $$x = 2y + 1 \quad\text{where}\quad x,y\in\mathbb Z$$ For even numbers: $$a = 2b \quad\text{where}\quad a,b\in\mathbb Z$$ But what about prime ...