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.
4
votes
2answers
121 views
Let $m^n-1$ be prime. What can $m$ be?
Let $m^n-1$ be prime. What can $m$ be if $m$ and $n$ are not $1$?
How can I find $m$?
0
votes
1answer
55 views
Smallest Mersenne prime with 100 million digits?
As some of you are probably aware, the Great Internet Mersenne Prime Search (GIMPS) is managing the search for the largest Mersenne primes of the form $M_p=2^p-1$, where $p$ is itself prime (GIMPS ...
2
votes
1answer
37 views
Understanding the pseudocode for the Sieve of Eratosthenes
The outer loop on the Wikipedia page for the Sieve of Eratosthenes ends at √n:
for i = 2, 3, 4, ..., √n :
Is this because if n has a square root it wont be prime? From what I understand this ...
5
votes
3answers
90 views
Size of largest prime factor
It is well known and easy to prove that the smallest prime factor of an integer $n$ is at most equal to $\sqrt n$. What can be said about the largest prime factor of $n$, denoted by $P_1(n)$? In ...
6
votes
6answers
2k views
Is a prime factor of a number always less than its square root?
I was going through the fundamental theorem in Number Theory where any non zero integer n can be represented as a product of distinct primes. A related problem with this theorem is to prove that for ...
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
47 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$ ...
9
votes
2answers
249 views
Doubt in finding number of non-prime factors of an integer
The question is:
Find the number of non-prime factors
of $4^{10} \times 7^3 \times 5^9$.
I represented the number as $2^{20} \times 7^3 \times 5^9$ then the number of factors of this integer ...
11
votes
2answers
386 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, ...
2
votes
2answers
85 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 ...
5
votes
3answers
155 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.
4
votes
2answers
90 views
Using sum of logarithms of primes to prove the number of primes up to $n$ is $O(n/\log n)$
I need to show that the number of primes up to $n$ (i.e. $\pi(n)$) is $O(n/\log n)$.
In the previous exercise of this question I proved that ${\displaystyle \sum_{i=1}^{\pi(n)}\log p_{i}} \leq Cn$ for ...
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 ...
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 ...
4
votes
3answers
222 views
How many cpus needed to check a 100 million digit prime number efficiently?
If I had access to potentially large number of CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the ...
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) = ...
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
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 ...
5
votes
4answers
4k views
What is a co-prime?
I've never encountered this question in any of my math classes and it just shows up randomly in my comsci class with no further info about it. I've wiki'ed it, but can't even understand that. Could ...
4
votes
4answers
145 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 ...
-3
votes
0answers
41 views
Not greater than what prime number value that can combine to all number under a value? [closed]
Assume the value is $10$, the prime value not greater than $3$, then use only $1,2,3$ can combine to any value in $\{1,2,3,4,5,6,7,8,9,10\}$ for example $8 = 2 + 2 \times 3$ or $2^3$
Actually this ...
1
vote
2answers
52 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 ...
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 ...
0
votes
1answer
53 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 ...
0
votes
1answer
179 views
Break RSA given a correct and faulty implementation
Suppose I have two machines, $A$ and $B$. $A$ encrypts a message $m$ and outputs the ciphertext $m^e \pmod n$. $B$ outputs $c$ such that $c = m^e \pmod p$ and $c = m^e + 1 \pmod q$. How can I use $A$ ...
7
votes
3answers
633 views
Proving a statement regarding a Diophantine equation
FINAL EDIT : Prove that if $p^z|n^2-1$
$$p^{x-z}(p^{z}-1)=\dfrac{ n^2-1}{p^z}-3$$ doesn't hold for any chosen values of $p,x,n$ and $z$.
Here $p>3$ is an odd prime , $x=2y+z, \ ...
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
57 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 ...
4
votes
4answers
149 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 !
0
votes
2answers
101 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
133 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, ...
4
votes
1answer
75 views
Understanding the gamma function in the context of Jitsuro Nagura's Proof
In 1952, Jitsuro Nagura published a classic proof that shows that for $n \ge 25$, there is always a prime between $n$ and $\frac{6n}{5}$.
For those interested the paper itself can be found here.
I'm ...
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.
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 ...
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!
1
vote
1answer
124 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 ...
4
votes
6answers
597 views
what is the ratio of number of prime to number of natural numbers
P is the count of prime numbers in Z
And so, Z-P=NP is the count of non-prime numbers in Z
what is the answer of this equation : P / NP
I thought that question and I made that proof, if im mistake ...
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 ...
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 ...
3
votes
1answer
123 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 ...
