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.
2
votes
3answers
38 views
Does there exist a k such that the kth prime is balanced in order k-1?
A balanced prime of order n is a prime number that is equal to the arithmetic mean of the nearest n primes above and below.
For example, 5 is a balanced prime in order 1 because it is the average of ...
6
votes
2answers
63 views
Need to state “$p$ not equal to $61$” when solving $61p + 1 = n^2$?
In the pictures below, am I wrong to say that the 3 lines in the red box are not needed in the solutions? Regardless of whether 61 and p are distinct, it's still true that we have only the 2 possible ...
0
votes
1answer
49 views
Find if a number $n$ is a primitive root of $p$
Let $n = p_1\cdot p_2\cdot\ldots\cdot p_k$ where the $p_i$ are primes. Let $s = \varphi(n)$ where $\varphi$ denotes the Euler Totient Function.
If none of $p_1,p_2,\ldots,p_k$ makes $a^{(s/p_i)} = 1$ ...
2
votes
2answers
86 views
Miller-Rabin Primality Test
I am trying to work out the potential primality of 341 using the Miller-Rabin algorithm. Below is as far as I get, I'm not really sure where to go from there. I believe I am supposed to use modular ...
11
votes
2answers
388 views
Has anyone found a “pattern” in prime numbers?
Yesterday I was having some fun trying to look for some patterns in primes; and I think I found something interesting (to me at least). I still have not found any lists of patterns already found, ...
5
votes
3answers
157 views
Integer solutions of $n^3 = p^2 - p - 1$
Find all integer solutions of the equation, $n^3 = p^2 - p - 1$, where p is prime.
1
vote
3answers
83 views
Prime number characterisation using congruences
I want to prove that $n$ is prime. From the Wilson's theorem it follows that $n$ is prime if and only if
$$(n-1)! + 1 \equiv 0 \pmod{n}$$
However, in my proof, I reduce the congruences to the ...
-1
votes
2answers
150 views
How to quickly check if a number is prime? [closed]
Let say I've found a very very very long prime number. I know it's prime but I need to have a proof. Is there any fast way how to check if a number is really prime?
Let say I've found the longest ...
5
votes
1answer
98 views
Understanding a famous proof by Jitsuro Nagura: Need help understanding one step in the main theorem
I am going through the proof by Jitsuro Nagura which shows that there is always a prime between $x$ and $\frac{6x}{5}$ where $x \ge 25$.
Nagura uses the following definitions:
$$\vartheta(x) = ...
3
votes
1answer
103 views
Is my proof correct? $p_1p_2p_3\cdots p_n+1)$ cannot be the square of an integer
Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer.
Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so ...
1
vote
2answers
53 views
Why is a prime number needed for the Diffie-Hellman key exchange? (modular arithmetic)
I'm writing a cryptography essay, and am wondering why you need a prime number for the deffie-hellman key exchange? Any help would be appreciated :)
this is a link to a previous post which quickly ...
3
votes
2answers
114 views
Prime numbers, what explains this pattern?
This morning I got a message on the Active Mathematica yahoo mailing list from the signature "in zero" asking to calculate this sum:
$$\sum _{k=1}^n \frac{\log (p_k)}{\log (p_n)}$$
where $p_n$ is ...
3
votes
2answers
85 views
Factorial primes
Factorial primes are primes of the form $n!\pm1$. (In this application I'm interested specifically in $n!+1$ but any answer is likely to apply to both forms.) It seems hard to prove that there are ...
2
votes
2answers
50 views
About linear combinations of primes
$a,b,c$ are natural numbers whose greatest common divisor is $1$.
$a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$
Try to write down the expression using $a,b,c$ of the biggest natural number $M$ that cannot be ...
4
votes
2answers
52 views
A set of numbers where none can be made by multiplying others in the set.
(I'm a programmer, please excuse my abuse of or lack of proper mathematical language)
The other day I needed to find a natural number that is cleanly divisible by all integers in the range ...
3
votes
1answer
78 views
Using Fermats Little Theorem to show $2^{17} -1$ is prime
Show that $n = 2^{17} - 1$ is prime by using Fermat's Little Theorem $2^{p-1} \equiv 1 \mod p$ for any $p$ dividing $n$.
I said, that by FLT, we get $2^{16} \equiv 1 \mod 17$, and we can see that ...
1
vote
0answers
26 views
conversion from psi function to prime counting function
Can we convert $\psi(x)$ to $\pi(x)$ without using integrals. Also if $\psi(x)>\psi(y)$
when we can say that $\pi(x)>\pi(y)$ . It seems that $\theta(x)>\theta(y)$ so $\pi(x)>\pi(y)$
but ...
4
votes
4answers
146 views
Is every prime number the leg of exactly one right triangle with integer sides? What's wrong with my argument that this is impossible?
The problem is: "prove that every prime number is the leg of exactly one right triangle with integer sides." However, I seem to have proved that this is impossible. What did I do wrong here?
Let ...
0
votes
1answer
54 views
How to test a real number a prime number
if $p^{1/n}$ where $p$ is a prime number and $n$ is an integer, will it be a prime number? should $n$ be prime?
for example $\sqrt3^{1/3}$, $\sqrt3^{1/10}$
what is the algorithm to test a real ...
3
votes
4answers
83 views
Formulae for both identifying or generating primes; Shows arranged distribution. Solved; basically trial division.
While looking at numbers and considering $n < p < 2n - 2$ and $p = 3n\pm 1$, where $p$ is any prime number, I was able identify a property for numbers $c=3n\pm 1$ where $c$ is a composite ...
2
votes
1answer
48 views
Inequality about prime numbers
I have been thinking about it lately. Let's think of prime number sequence: $$q_1,q_2,...q_n$$ where $q_1=2, q_2=3$ and onwards. Can we find an n such as the inequality $$q_n \gt ...
4
votes
2answers
61 views
$(p-2)!-1 \neq p^k$ for any $k\in \mathbb{N}$, $p$ is a prime.
$(p-2)!-1 \neq p^k$ for any $k\in \mathbb{N}$, $p>5$, $p$ is a prime.
How to solve this?
2
votes
0answers
29 views
$\sum_{i=1}^{k}[\sqrt{ip}]=\frac{p^2-1}{12}$, $p$ is a prime of the form $4k+1$ [duplicate]
$\sum_{i=1}^{k}[\sqrt{ip}]=\frac{p^2-1}{12}$, $p$ is a prime of the form $4k+1$
How to prove this?
2
votes
1answer
59 views
Prove the converse of Wilson's Theorem
... namely that if $n > 1$ and $(n − 1)!\equiv−1\pmod{n}$, then $n$ is prime.
This is for a number theory class I'm in at Penn State. My idea is to follow accordingly, but I can't get it ...
2
votes
1answer
57 views
Density of semiprimes on short intervals
Perhaps this is a trivial question, but I'm not an expert. Let
$$Q(m) = \bigl| \{ n : m\leq n \leq m + \log(m) \mbox{ and } n = p \cdot q\text{, where }p,q\text{ are prime} \} \bigr|$$
i.e., $Q(m)$ ...
4
votes
4answers
151 views
Why 4 is not a primitive root modulo p for any prime p?
I wonder why 4 is not a primitive root for any prime p ?
I've been trying to find an answer with no success so far. Any suggestion would be very helpful,
thanks in advance !
-1
votes
3answers
120 views
Quantum uncertainty can explain the Riemann Hypothesis?
In the recent paper "Riemann Hypothesis as an Uncertainty Relation" (http://arxiv.org/abs/1304.2435) the author claims that the presence of zeros out of the critical line may lead to the violation of ...
3
votes
0answers
43 views
Efficiency in factoring lists of consecutive numbers
Suppose I'm looking at prime factorizations of numbers in the vicinity of this one:
$$
1354 = 2 \times 677
$$
The smallest prime appears here, and the next prime after that does not.
Going one step ...
4
votes
3answers
134 views
Show that there exists $f ∈ \mathbb{Z}$ such that $f^2 + f +1 ≡ 0 \pmod p$.
Let $p ≡ 1 \pmod 3$ be a prime. Show that there exists $f \in \mathbb{Z}$ such that $f^2 + f +1 \equiv 0 \pmod p$.
I know the first few primes of this form are: $7,13,19$
So for example $p=7$ we ...
7
votes
2answers
131 views
Find all values x, y and z which satisfy the equation $(x^2 + 1)(y^2 + 1) = z^2 + 1$ given that $(x^2 + 1)$ and $(y^2 + 1)$ are both primes.
Find all positive integers x, y, z which satisfy the equation $(x^2 + 1)(y^2 + 1) = z^2 + 1$ given that $(x^2 + 1)$ and $(y^2 + 1)$ are both primes.
It seems trivial that the only set of integers x, ...
2
votes
3answers
76 views
Wiki proof of Lucas primality test
I have a question about one step in the proof:
Why does $a^{n-1} \equiv 1\ (\operatorname{mod} n)$ imply that $a$ and $n$ are coprime?
Thank you!
32
votes
6answers
2k views
Is $2^{218!} +1$ prime?
Prove that $2^{218!} +1$ is not prime.
I can prove that the last digit of this number is $7$, and that's all.
Thank you.
21
votes
0answers
420 views
Generalizing Ramanujan's proof of Bertrand's Postulate: Can Ramanujan's approach be used to show a prime between $4x$ and $5x$ for $x \ge 3$
Perhaps, I've been thinking too long about Ramanujan's proof, but it appears to me that his argument can be generalized beyond $x$ and $2x$. My argument below attempts to show that for $x \ge 1331$, ...
5
votes
2answers
101 views
Very interesting Number Theory problem
Let $a>3$ be an odd integer. Prove that for every positive integer $n$, the number $a^{(2^{n})}-1$ has at least $n+1$ distinct prime divisors.
This problem smells very strongly of induction, but ...
4
votes
2answers
52 views
Sum involving prime numbers
Given the series:
$$S=\sum_{k=1}^{N}\frac{k}{p_k}$$
where $p_k$ is the $k^{th}$ prime number, is it possible to know if this series converges in the limit:
$$\lim_{N\to\infty}S$$
and eventually, its ...
10
votes
2answers
136 views
About prime factor and consecutive integers
The problem is:
There exists an integer $N$ such that for any $n>N$, there exists $m \in \{n,n+1, \ldots ,n+9\}$ such that $m$ has at least $3$ distinct prime factors.
2 Years ago, My ...
3
votes
1answer
126 views
The meaning of the Euler Formula for Zeta
Does anybody know about a "meaning" behind the Euler Formula, what does it really say about the primes?
I know that it is in equation to the zeta function and also how it is derived, but cannot find ...
0
votes
0answers
40 views
General term of this sequence
I wanted to know the General term or the function to generate this sequence I found on OEIS.
It is the number of ways to express 2n+1 as p+2q; where p and q can be odd prime number and even semiprime ...
5
votes
1answer
54 views
Euler's proof for the infinitude of the primes
I am trying to recast the proof of Euler for the infinitude of the primes in modern mathematical language, but am not sure how it is to be done. The statement is that:
$$\prod_{p\in P} ...
3
votes
1answer
69 views
Proof showing there exists a sequence of $m$ consecutive natural numbers which contains exactly $n$ primes.
Given that $n\in\Bbb N$, show that there exists a $k\in\Bbb N$ such that for all $m\ge k$, there exists a sequence of $m$ consecutive natural numbers which contains exactly $n$ primes.
1
vote
1answer
125 views
Gamma function in Taylor series
The formula I am having some problems is this one
$$
f\left( x \right) =\sin \left(\frac { 2(x-3)!-x+1 }{ 2x } \pi \right) =\sin \left(\frac { 2\,\Gamma (x-2)-x+1 }{ 2x } \pi \right)
$$
Although ...
3
votes
4answers
75 views
How to derive this expression $ r ^{ (p-1)/2} \equiv -1 \pmod p$ for primitive root of an odd prime $p$.
While studying Elementary Number theory by David M. Burton I came across this line:
because $r$ is a primitive root of $p$, $$ r ^{ (p-1)/2} \equiv -1 (\mod p) $$ where $p$ is an odd prime.
...
7
votes
2answers
68 views
Need help on Furstenberg's proof on the infinitude of primes
I have a question on this proof given by Furstenberg proof on the infinitude primes. I am a non-mathematician with some basic knowledge on set theory and topology.
Define for $a,b\in\mathbb{Z}$ where ...
8
votes
0answers
220 views
Understanding Ramanujan's approach in his proof of Bertrand's Postulate
I've been reading through Ramanujan's proof of Betrand's Postulate and I'm not clear why he didn't state his proof in terms of $\varphi(2x) - \varphi(x)$
What would be wrong with this approach for ...
1
vote
2answers
52 views
Number of proper divisors generally prime
If we count the number of proper divisors of a positive integer, why do we usually get a prime number (or $1$)?
...
0
votes
1answer
40 views
Find all base $b$ of both pseudoprimes $15$ and $21$
Find all bases $b$ such that $15$ and $21$ are pseudoprimes,i.e.
$b^{14} \equiv 1 (mod 14)$ and $b^{20} \equiv 1 (mod 20)$
Can anyone help me?
1
vote
1answer
59 views
Dirichlets theorem on primes
I want to use Dirichlets theorem on primes for my diploma thesis. I want to use following form
Let $a,b\in\mathbb{N}$, such that $\gcd(a,b)=1$. Then the set $\{a\cdot n+b| n\in\mathbb{N}\}$ contains ...
1
vote
1answer
41 views
Missing one link in logic of basic unique factorization argument
From page 2 of The Prime Facts : from Euclid to AKS by Scott Aaronson :
Thus P/A = R/K. But R is less than P, since it’s a remainder from dividing by P.
Okay
So P/A can’t be in lowest ...
0
votes
0answers
35 views
How do I find $m^q\pmod p$ if I already have the following values
I have $g^k\pmod p$, $m\cdot h^k\pmod p$. I also know that $g$ is ìn the set $\{1, 2, \cdots, p-1\}$ and $g$ is of order $q$, so I believe that means that $g^q = 1\pmod p \Rightarrow 1 = g^q\pmod p$. ...
1
vote
1answer
48 views
Find all expressions of a prime as a sum of four squares
Does anyone know an efficient algorithm to compute all solutions of
$$
x^2 + y^2 + z^2 + w^2 = p
$$
where $x, y, z, w \in \mathbb{Z}$ and $p \in \mathbb{P}$?
By efficient I mean linear on the number ...
