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

1
vote
0answers
187 views

Fourier Analysis of Prime Counting Function

I was thinking about the following: Denote $\pi(x)$ as the prime counting function such that: $$ \pi(x) = \#\text{ of prime numbers}\leq x $$ It is well known from the prime number theorem that $$ ...
1
vote
1answer
194 views

Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number

Prove or disprove: There exists an integer $k\geq 4$ such that $2k^2 -5k+2$ is a prime number. If true (which I'm pretty sure it isn't), then the proof needs to be in either contradiction or ...
5
votes
1answer
121 views

Does this have a name: If an odd prime $p$ does not divide $a$, then $p$ divides $a^n + 1$ or $a^n - 1$

After seeing and doing a bunch of proofs like "For all $a$ in the natural numbers, then if $7$ does not divide $a$, then $7$ divides $a^3+1$ or $a^3-1$," I conjectured the following, but got stuck in ...
1
vote
1answer
89 views

Research on $\log(p)$? [closed]

We are searching for articles, research work or interesting interpretations/applications of $\log(p)$ where $p$ a prime. It should not be only limited to math, contributions from physics are also ...
2
votes
1answer
422 views

Euler's totient function maximum value for a range [duplicate]

For the euler's totient function, we have a number $n<10^{18}$ we have to find the value of $i$ between $2$ and $n$ (both inclusive) such that the value of $\phi(i)/i$ is maximum. I have have ...
6
votes
1answer
296 views

Hamlet to be or not to be in Primes?

It is conjectured that, if you read $\pi$ long enough you'll find Hamlet. Since other numbers, like the Copeland–Erdős constant are known to be normal in base $10$, it should be true at least there. I ...
2
votes
1answer
393 views

What software can calculate the order of $b \mod p$, where $p$ is a large prime?

I wasn't sure where to ask this, but Mathematics seems better than StackOverflow or Programmers. I have no background whatsoever in number theory, and I need to find software that can calculate the ...
23
votes
1answer
338 views

Is any closed-form representation known for the sum $\sum\limits_{n=1}^{\infty}\frac{\mu(n)\log n}{n^2}$?

Is any closed-form representation known for the sum $\sum\limits_{n=1}^{\infty}\frac{\mu(n)\log n}{n^2}$, where $\mu(n)$ is the Möbius $\mu$-function?
3
votes
2answers
170 views

A question about the Andrica's conjecture on the prime numbers

The Andrica's conjecture on the prime numbers states: given a couple of prime numbers $p_k$ and $p_{k+1}$ the following inequality holds: $$\sqrt{p_{k+1}}-\sqrt{p_{k}}\lt 1$$ Is it possible to show ...
12
votes
1answer
414 views

Prove that $\sum\limits_{i=0}^{k} p^{2i}$ ($p$ is prime) is never a perfect square

Prove that $$ \sum_{i=0}^{k} p^{2i} $$ where $k > 0$ and $p$ is an arbitrary prime, is never a perfect square. I think you can prove it by letting $q = \sum\limits_{i=0}^k a_ip^i$, then expanding ...
1
vote
1answer
85 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.
4
votes
2answers
143 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$?
5
votes
1answer
350 views

Is this number theory conjecture known to be true?

I've been working on proving that there is always a prime between $n$ and $2n$, and also that there is always a prime between $n^2$ and $(n+1)^2$ (Legendre's conjecture). I believe I've proven those ...
7
votes
3answers
174 views

Finding a prime number between $n$ and $2n$

I am trying to find a prime number between $n$ and $2n$. I know that the number of primes between $n$ and $2n$ is $n/(2\ln n)$. I was thinking of choosing a random number between $n$ and $2n$ and ...
0
votes
1answer
144 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
611 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 ...
9
votes
3answers
631 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 ...
2
votes
3answers
66 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
70 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
102 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$ ...
3
votes
3answers
340 views

Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)

Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which ...
2
votes
2answers
303 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 ...
19
votes
2answers
11k 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
2answers
306 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
122 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
342 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
134 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
150 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
139 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 ...
5
votes
2answers
258 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
498 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
3answers
350 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
81 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 ...
4
votes
1answer
168 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
53 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
451 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 ...
4
votes
4answers
148 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
36 views

Calculate total number of matrices of all orders which contain $2013$ elements

Calculate total number of matrices of all orders which contain $2013$ elements My Try:: By Simple Guessing wecan say that there are two matrices of order $(1\times 2013)$ and $(2013 \times 1)$ ...
2
votes
1answer
95 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
68 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
35 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?
3
votes
1answer
1k 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 ...
3
votes
1answer
157 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
561 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 !
-2
votes
3answers
217 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
1answer
163 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
145 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
308 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, ...
1
vote
3answers
192 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!
36
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.