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.
5
votes
3answers
228 views
What would be the immediate implications of a formula for prime numbers?
What would be the immediate implications for Math (or sciences as a general) if someone developed a formula capable of generating every prime number progressively and perfectly, also able to prove (or ...
6
votes
0answers
344 views
Partial Solution to the Twin Primes Conjecture — What does it imply? [closed]
But now, as the Mathematician Zhang Yitang from University of New Hampshire in Durham has shown, there is a kind of weak version of the twin prime conjecture. He didn’t prove that a distance of 2 ...
3
votes
3answers
293 views
Is it true that all senary numbers ending in 1 and 5 are primes?
I was reading the Wikipedia article on senary numbers (base 6), which states that:
all primes, when expressed in
base-six, other than 2 and 3 have 1 or
5 as the final digit
Unless I am ...
3
votes
1answer
74 views
Why is $n=\frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r}$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$
Why is $n= \left\lfloor \frac{2p^2+2pq+2pr+q^2+2qr+r^2}{p+q+r} \right\rfloor$, where $n$ is $\text{prime}$, of form such that $p\pm a,p\pm b,$ are $ \text{prime}, 1<a<b<n$?
Consider this:
...
2
votes
0answers
126 views
primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$
I have trouble showing that primes of the form $p=8k+1, 8k+3$ can be expressed as $p=a^2+2b^2$.
Thanks in advance.
10
votes
3answers
476 views
Cardinality of the set of prime numbers
It was proved by Euclid that there are infinitely many primes. But what is the cardinality of the set of prime numbers ?
Cantor showed that the sets $\mathbb{Q}$ and $\mathbb{Z}$ have the same ...
-6
votes
0answers
53 views
Creation of Prime numbers [closed]
Suppose I have a set of 4 algebraic equations (none exceeding the second order) which create ALL Prime numbers.
A breakthrough or not?
Constantine
0
votes
1answer
45 views
Why is $\{n=4r+1,r = {n-1\over 2}\}\subset \mathbb{P}$ true under these conditions?
Let $p=p_k$, $q=p_{k+1}$ and $r=p_{k+2}$, where $p_m$ denotes the $m$th prime.
I conjecture that whenever $n$ is prime, where $n$ is defined as follows:
$$n = 1+\left(\left\lfloor{p\over ...
1
vote
2answers
42 views
Proving x and y is divisible by p (prime).
If p is a prime number and x and y are integers, how do I prove "if xy and x+y are both divisible by p, then x and y is divisible by p"?
I started like this..
1) p divides xy, so p divides x or p ...
0
votes
0answers
25 views
Tight bounds on the prime counting function
What are the best bounds for $\pi(x)$ i.e. the number of primes less than or equal to $x$ ?
From Wikipedia I saw that:
$$\frac{x}{\ln x}\left(1 + \frac{1}{\ln x}\right) < \pi(x) < \frac{x}{\ln ...
5
votes
7answers
590 views
Prime number generator, how to make
Can anybody point me an algorithm to generate prime numbers, I know of a few ones (Mersenne, Euclides, etc.) but they fail to generate much primes...
The objective is:
given a first prime, ...
1
vote
0answers
38 views
Revised: Primes of form $p \equiv m \in S \mod x \ $
Refer to this question for background.
I was speculating if there was an elegant way to define sequences
A007645,A002313,A045357,A045407,A042986,A045331,
A045425,A045374,A045400,A045350,A042988;
...
4
votes
3answers
47 views
Infinitely many primes of the form $4n+3$
I've found at least 3 other posts$^*$ regarding this theorem, but the posts don't address the issues that I have.
Below is a proof that for infinitely many primes of the form $4n+3$, there's a few ...
1
vote
1answer
53 views
Regarding definition of cuban primes
While considering the relationship between $6n-1$ (OEIS A002476) and generalized cuban primes(OEIS A007645) I came across something I thought was interesting:
Seems like the description of ...
3
votes
2answers
51 views
effective version of Mertens Theorem for the Euler product
I'm referring to the theorem given here, which is
$$\displaystyle\lim_{n\to \infty} \:\: \left(\frac1{\ln(n)} \cdot \left(\displaystyle\prod_{p\leq n} \frac1{1-\frac1p}\right)\right) \;\;\; = \;\;\; ...
1
vote
0answers
30 views
Could a determinstic primality test specialized to this form of prime exist?
Is it possible there could be an "efficient" deterministic primality test for prime numbers of the form
$$(2^n + 1)^2 - 2$$
or
$$(2^n - 1)^2 - 2$$
in the same vein as the Lucas-Lehmer test for ...
12
votes
5answers
604 views
How many prime numbers are known?
Wikipedia says that the largest known prime number is $2^{43,112,609}-1$ and it has 12,978,189 digits. I keep running into this question/answer over and over, but I haven't been able to find how many ...
3
votes
0answers
70 views
Prime norm ideals that are also principal
Landau's prime number theorem tells us asymptotic formula for counting the number of prime ideals of a number field K, with norm at most X.
I am interested in the the prime ideals with a prime norm. ...
3
votes
1answer
64 views
On the primality of integers of the form $p^2+k$
I am not able to find an answer to the following question:
For which positive even integers $k$ is the integer
$$p^2+k$$ prime, where $p$ is a prime number $\gt5$?
14
votes
3answers
328 views
An Elementary Number theory Problem
A mathematician friend gave me this question (partly as a joke) a few months ago and it has puzzled me for a long time:-
Do there exist infinitely many pairs of primes $(p,q)$ such that ...
1
vote
1answer
56 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.
1
vote
2answers
43 views
Classify the odd primes $q$ such that a NEGATIVE number is a quadratic residue $\mod{q}$
Suppose we are given $y < -1$. I wish to classify all primes $q$ such that $y$ is a quadratic residue $\pmod{q}$, i.e. such that there exists a number $x$ satisfying $$y \equiv x^2 \pmod{q}.$$
How ...
2
votes
1answer
51 views
Finding a prime $p$ to solve a quadratic congruence $\pmod{p}$
I have a congruence of the form $$ax^2+bx \equiv -1 \pmod{p},$$
where $p$ is an odd prime and $a,b \in \mathbb{Z}$. Given $a$ and $b$, is there a general method to finding $p$ such that the above ...
2
votes
0answers
41 views
Unique decomposition of $c$ sums of products of $k$ numbers greater than 1, allowing duplicates?
This question differs from Unique decomposition of $c$ sums of products of $k$ prime numbers, allowing duplicates? in that prime number restriction is changed to any number greater than 1.
Suppose ...
3
votes
1answer
52 views
$\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$.
How to prove that $\sigma(\sigma(p^2)) \neq 2p^2$ for all odd primes $p$?
I know that $\sigma(p^2)=1+p+p^2$ but I can't progress anymore.
2
votes
3answers
40 views
Marking the prime points on a circle
If you travel around a circle and mark all the points on the circle where the distance you travelled is a prime number, where you would go through many rotations*, do you end up marking the entire ...
2
votes
2answers
40 views
Why must a and p be relatively prime in Fermat's Little Theorem?
A variant of Fermat's Little Theorem states that $a^{p - 1} \equiv 1~mod~p$ if $a$ is not divisible by $p$.
Why is this last condition important? Why must $a$ and $p$ be relatively prime?
3
votes
2answers
48 views
Existence of a prime
If $x$ is odd and natural and ${x^2}+2\equiv3\mod 4$, how can I show there exists a prime $p$ such that $p|x^2+2$ and $p\equiv3\mod 4$.
-1
votes
0answers
53 views
Fermat's Primality Test returning 29 as a non-prime number [closed]
I'm using this page on Wikipedia as a guide to implement this algorithm. I've tried debugging this code but I can't figure out why it doesn't work for 29:
...
0
votes
0answers
104 views
Weak Goldbach conjecture for large integers
Why do there is a number around $n\approx e^{3100}$ such that every odd number larger that $n$ is a sum of three primes? I was unable to find a proof on the Internet so a sketch of the proof would be ...
2
votes
0answers
69 views
How to find prime numbers
I am looking for a formula that tells me what the next prime number will be. It is hard to do this without a formula because for example there is a small gap between 17 and 19 then a big one between ...
2
votes
0answers
42 views
Unique decomposition of $c$ sums of products of $k$ prime numbers, allowing duplicates?
Suppose that there are $n$ different prime numbers. Define procedure a) as following ($k \leq n$ and $k$ fixed): procedure a) for each time, we select one number out of $n$ possible cases and multiply ...
8
votes
3answers
189 views
Proof of Wolstenholme's theorem.?
According to the theorem :
$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{p-1} =\frac{r}{q}$$
And we have to prove that $r= 0 \pmod{p^2}$.
(Given $ p>3$, ...
1
vote
2answers
123 views
Where can one find a list of prime numbers?
I am looking for the biggest list of precomputed prime numbers one can find and download. Where should I look?
2
votes
1answer
49 views
The set of exponential primes
Consider a set of integers $Q$ such that the set of all positive integers $\mathbb{Z}$ is equivalent to the span of ever possible power tower
$$a_1^{a_2^{\ldots a_N}}$$ involving $a_i \in Q$.
In ...
2
votes
1answer
44 views
Sequence of primes.
This is a previous year question and I have no idea how to start.
Let $p_1<p_2<....<p_{31}$ be prime numbers such that $30$ divides $\sum_{i=1}^{31}p_i^4$.
Prove that $p_1=2, ~p_2=3 , ...
2
votes
0answers
84 views
Prime numbers with binomial coefficients
Let $p$ be an odd prime and $n$ a positive integer. Prove that $p+1$ divides $n$ if and only if $$\sum_{k\equiv j\pmod{p-1}}^n^{}\binom{n}{k}(-1)^{\frac{(k-j)}{p-1}}\equiv 0 \mod p$$
for every $$j\in ...
3
votes
2answers
68 views
How to calculate prime numbers.
As a practice applciation, I am trying to write a prime number calculator that would be able to given a number, for example "124981242424", determine the nearest prime number and give me the ten next ...
0
votes
4answers
74 views
Let ${P_n}$ be the sequence of all consecutive prime numbers. Is $\sum_{n\geq 1} \frac{1}{p_n}$ convergent? [duplicate]
Let ${P_n}$ be the sequence of all consecutive prime numbers. Is $\sum_{n\geq 1}\frac{1}{p_n}$ convergent?
4
votes
1answer
42 views
Binomial theorem for prime exponent
Could you explain to me why for prime $p$ we have the following?
$$(x+y)^p - (x^p + y^p)= x^p + \binom{p}{1}x^{p-1}y + \binom{p}{2}x^{p-2}y^2 + \binom{p}{p-1}xy^{p-1} + y^p.$$
I found it here: ...
2
votes
0answers
54 views
Making fermat's little theorem for composite numbers the ultimate test.
It is a programming question but mathematics has a major role to play in it.
I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem ...
5
votes
1answer
50 views
Prime numbers with binomial coefficients
Question:
Prove that for any prime $p>3$, the number $\binom{2p-1}{p-1}-1$ is divisible by $p^{3}$.
Attempt:
Since every integer that is relatively prime to p has a multiplicative inverse
modulo ...
1
vote
1answer
67 views
Proof regarding prime numbers:
THEOREM:
If a prime $p$ divides a product $a_1 \cdot \cdot \cdot a_n$, then $p$ divides at least one of its factors, $a_i$.
This is my attempt at the proof, the book I am reading from suggests ...
0
votes
2answers
60 views
Is it true that $a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;$?
$$a^{k(p-1)+b} \;\stackrel{p}{\equiv} \;\;a^b\;?$$
$p$ prime number and $a,b,k\in\mathbb{N}^+$. And $p$ does not divide $a$.
According to Fermat's Little theorem $a^{p-1}\stackrel{p}{\equiv}1$. So ...
8
votes
3answers
159 views
Number theory: Prime powers and cubes
Determine all triples $(p,a,b)$ of positive integers, where $p$ is prime and $a \leq b$ such that $$p^a+p^b$$ is a perfect cube.
I came across this question while looking at past maths Olympiad ...
10
votes
1answer
210 views
Can the order of 2 mod p be arbitrarily small (relative to $p - 1$)?
Given a prime number $p$, let $\operatorname{ord}_p(2)$ be the multiplicative order of $2$ modulo $p$, i.e., the smallest integer $k$ such that $p$ divides $2^k - 1$. By Lagrange's theorem, ...
0
votes
0answers
28 views
Is there a pair correlation function for primes?
Montgomery's pair correlation function for the non-trivial zeros of the Riemann $\zeta(s)$ function is defined via the term $$1- \left( \frac {\sin(\pi u)}{\pi u} \right)^2$$
Does anybody know if ...
1
vote
0answers
54 views
Randomness in prime numbers
I'm very interested in possible randomness in prime numbers distribution. There are many methods for
"decomposition" regularity and randomness in primes (e.g. subtraction of some asymptotics , ...
1
vote
1answer
65 views
Average of divisors of n.
Let n be a natural number and let $f(n)=\frac{\sigma(n)}{d(n)}$ be the arithmetical average of n's divisors. Either prove or give a counterexample that for all natural numbers like n, which are not ...
1
vote
0answers
46 views
Consequencesof the Hadamard product expression of $L(s, \chi)$
I'm going through my lecture notes and I'm stuck on the proof of
For any $t>0$ and primitive $\chi$ modulo $q$
$$\sum_{\rho=\beta+i \gamma: \Lambda(\rho, ...
