Prime numbers are natural numbers greater than 1 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

16
votes
6answers
22k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?
16
votes
6answers
1k views

Prove $a+b+c+d $ is composite

Let $a,b,c,d$ be natural numbers with $ab=cd$. Prove that $a+b+c+d$ is composite. I have my own solution for this (As posted) and i want to see if there is any other good proofs.
16
votes
3answers
2k views

Is every positive nonprime number at equal distance between two prime numbers?

For example $8$ is in the middle of the interval between $5$ and $11$, $9$ is at equal distance between $7$ and $11$; $10$ between $7$ and $13$.
16
votes
2answers
508 views

Prove that for any nonnegative integer n the number $5^{5^{n+1}} + 5^{5 ^n} + 1$ is not prime

My math teacher gave us problems to work on proofs, but this problem has been driving me crazy. I tried to factor or find patterns in the numbers and all I can come up with is that for $n > 0$, the ...
16
votes
4answers
1k views

Proof that there are infinitely many prime numbers starting with a given digit string

To prove the following fact: given any sequence of digits in any base, eg 314159265358979323 base 10, there are infinitely many primes that start with these digits,eg when expressed in decimal they ...
16
votes
2answers
834 views

Is there an infinite number of primes constructed as in Euclid's proof?

In Euclid's proof that there are infinitely many primes, the number $p_1 p_2 ... p_n + 1$ is constructed and proved to be either a prime, or a product of primes greater than $p_n$. Trivially, we ...
16
votes
2answers
2k views

Can every even integer be expressed as the difference of two primes?

Can every even integer be expressed as the difference of two primes? If so, is there any elementary proof?
16
votes
3answers
557 views

Solving $p_1^{e_1} p_2^{e_2}…p_k^{e_k}=e_1^{p_1} e_2^{p_2}…e_k^{p_k}$

Find all positive integers $k$, positive integers $e_i$, and distinct prime numbers $p_i$ for $1\le i\le k$, such that $$p_1^{e_1} p_2^{e_2}...p_k^{e_k}=e_1^{p_1} e_2^{p_2}...e_k^{p_k}.$$ Is this ...
16
votes
1answer
198 views

$|3^a-2^b|\neq p$, from a contest

I recently came across an old contest problem: (I did not find the solution anywhere) Find the least prime number which cannot be written in the form $|3^a-2^b|$ where $a$ and $b$ are ...
16
votes
2answers
360 views

Geometric mean of prime gaps?

The arithmetic mean of prime gaps around $x$ is $\ln(x)$. What is the geometric mean of prime gaps around $x$ ? Does that strongly depend on the conjectures about the smallest and largest gap such as ...
16
votes
1answer
3k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
16
votes
2answers
360 views

Is this olympiad-like question about remainders an open problem?

Suppose that we are given two positive integers $x$ and $y$ such that $$x \mod p \leqslant y \mod p$$ for each prime number $p$. (Here, $x \mod p,\; y \mod p$ stand for the least non-negative ...
15
votes
6answers
3k views

Is an arbitrary number of the form xyzxyz divisible by 7, 11, 13?

So I was given this question Choose any 3-digit number xyz and write it after itself as follows: xyzxyz. Check whether it is divisible by 7,11, 13. Is an arbitrary number of the form xyzxyz ...
15
votes
5answers
1k views

Is that true that all the prime numbers are of the form $6m \pm 1$?

Is that true that all the prime numbers are of the form $6m \pm 1$ ? If so, can you please provide an example? Thanks in advance.
15
votes
4answers
816 views

Prove that $n^2+n+41$ is prime for $n<40$

Here's a problem that showed up on an exam I took, I'm interested in seeing if there are other ways to approach it. Let $n\in\{0,1,...,39\}$. Prove that $n^2+n+41$ is prime. I shall provide my ...
15
votes
4answers
1k views

Prove there are no prime numbers in the sequence $a_n=10017,100117,1001117,10011117, \dots$

Define a sequence as $a_n=10017,100117,1001117,10011117$. (The $nth$ term has $n$ ones after the two zeroes.) I conjecture that there are no prime numbers in the sequence. I used wolfram to find the ...
15
votes
3answers
459 views

A prime of the form $38111111\ldots$

Let $z(n)$ denote the number given by $38$ followed by $n 1$'s. What is the least number $n$, such that $z(n)$ is prime ? With brute force, I checked up to $7000$ digits and did not find a prime. ...
15
votes
5answers
4k views

Proving that there are infinitely many primes with remainder of 2 when divided by 3

I need to prove that there are infinitely many primes with remainder of 2 when divided by 3. I started out similarly to Euclid's classic proof of an infinite number of prime numbers: Suppose there is ...
15
votes
3answers
1k views

Use this sequence to prove that there are infinitely many prime numbers. [duplicate]

Problem: By considering this sequence of numbers $$2^1 + 1,\:\: 2^2 + 1,\:\: 2^4 + 1,\:\: 2^8 +1,\:\: 2^{16} +1,\:\: 2^{32}+1,\ldots$$ prove that there are infinitely many prime ...
15
votes
1answer
1k views

Is there a prime number between every prime and its square?

For each prime number $p$, is there always an other prime number between $p$ and $p^2$ ? I tested it for prime numbers $< 500,000,000$, but I wanted to know if there is any mathematical proof of ...
15
votes
1answer
527 views

Is it possible to assign a value to the sum of primes?

It is possible, by means of zeta function regularization and the Ramanujan summation method, to assign a finite value to the sum of the natural numbers (here $n \to \infty $) : $$ 1 + 2 + 3 + 4 + ...
15
votes
3answers
1k views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime A supreme ...
15
votes
2answers
259 views

Primes of form $a^2 + 24b^2$

For a prime number $p \neq 2$, $3$, is it necessarily the case the prime number can be written in the form $a^2 + 24b^2$ if and only if $p \equiv 1 \text{ mod }24$? I think this has to be true based ...
15
votes
4answers
682 views

Need help understanding Erdős' proof about divergence of $\sum\frac1p$

I'm looking at proofs from Proofs from the Book (Martin Aigner, Günter M. Ziegler). The proof I'm having trouble is the sixth proof of the infinitude of the primes they give (on page 5; although I'll ...
15
votes
2answers
692 views

Is there a better upper bound for the primorial $x\#$ than $4^x$

In the classic proof of Bertrand's postulate by Paul Erdős, he shows that $x\# < 4^x$ where $x\#$ is the primorial for $x$. Is there any tighter upper bound for a given primorial $x\#$? Ideally, ...
15
votes
1answer
608 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, ...
15
votes
1answer
423 views

Proof of infinitude of primes using the irrationality of π

According to the section Proof using the irrationality of $\pi$ of the Wikipedia article on Euclid's theorem, Euler proved that: ...
15
votes
1answer
394 views

Primey Pascal's Triangle

Imagine that we have a triangle that starts with 2,3 and grows like Pascal's triangle but instead uses the smallest prime $\geq$ to the sum of the above two primes. Visually: $$ ...
15
votes
2answers
211 views

why $ \rm{lcm}[1,2,3,\cdots,n]\in (2^n,4^n)$

Let $n\ge 7$ be positive integers,show that $$f(n)=\rm{lcm}[1,2,3,\cdots,n]\in (2^n,4^n)$$ Anyone know this problem background?or maybe have best proof or best result?
15
votes
1answer
1k views

If the abc conjecture has been proven what implication does that have for elliptic curve cryptography?

I am not a mathematician, but I was wondering if the proposed proof of the abc conjecture (PDF) by Shinichi Mochizuki of Kyoto University would contain insights and mathematical tools that would lead ...
15
votes
1answer
383 views

Are all primes Euclid primes?

I was learning Euclid's theorem. If we repeat his construction (properly modified to give only primes) then will we skip any primes? Formally: $p_1 = 2$, and $p_{n + 1} = \text{smallest} \; q \in ...
15
votes
1answer
595 views

Going from $\Lambda$ to a prime count

A 1997 paper of Étienne Fouvry and Henryk Iwaniec, Gaussian primes, concerns the prevalence of primes that are of the form $n^2+p^2$ for prime $p$. The asymptotic result is $$\sum_{n^2+p^2\le ...
15
votes
0answers
405 views

A question about the divisibility of sum of 2 consecutive primes.

Well as I was curious about the sum of $2$ consecutive primes, after proving that the sum for the odd primes always has at least 3 prime divisors, I came up with this question: Find the least ...
14
votes
6answers
3k 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 ...
14
votes
1answer
1k views

Finding smallest and largest prime factor of $\frac{200!}{180!}$

I originally started off by listing all the primes: $p<200$ then trying to calculate the prime factorisation of each (which I realise is a silly thing to do) I believe there must be a simpler way ...
14
votes
3answers
399 views

$\sum\limits_{\text{prime }p} 2^{-p}$ is an irrational number

I need help to prove the following result. $\displaystyle\sum_{\text{prime }p} 2^{-p}$ is an irrational number.
14
votes
4answers
751 views

Why do repunit primes have only a prime number of consecutive $1$s?

Repunit primes are primes of the form $\frac{10^n - 1}{9} = 1111\dots11 \space (n-1 \space ones)$. Each repunit prime is denoted by $R_i$, where $i$ is the number of consecutive $1$s it has. So far, ...
14
votes
2answers
1k views

Evidence against Goldbach's Conjecture?

It recently occurred to me that, unless I'm much mistaken, Goldbach's conjecture can easily be seen to be equivalent to a seemingly more general statement: Every number $n$ divisible by any ...
14
votes
1answer
181 views

What is the significance of the power of $3$ in the sequence of primes given by $\lfloor A^{3^n}\rfloor ?$

Mill's constant is a number such that $\lfloor A^{3^n}\rfloor$ is prime for all $n$. The existence of such an $A$ was proven in $1947$. I know little about number theory, but I am curious as to why ...
14
votes
3answers
568 views

Are the logarithms in number theory natural?

I find the frequent emergence of logarithms and even nested logarithms in number theory, especially the prime number counting business, somewhat unsettling. What is the reason for them? Has it maybe ...
14
votes
1answer
438 views

German sofa primes: Can both $q$ and $\frac{q^3+1}{2}$ be prime?

Is there an odd prime integer $\displaystyle q$ such that $\displaystyle p= \frac{q^3+1}{2}$ is also prime? A quick search did not find any, nor a pattern in the prime factorization of p. This ...
14
votes
2answers
258 views

An upper bound for $\log \operatorname{rad}(n!)$

Let $n>1$ be an integer and let $\operatorname{rad}(n!)$ denote the radical of $n$-factorial. (The radical of an integer $m$ being, loosely speaking, the product of the prime divisors of $m$.) Can ...
14
votes
1answer
3k views

Prime with digits reversed is prime?

Well, just another idea came up into my mind and i have no idea how to solve it :D Is there infinitely many prime numbers, which are not repunits and their inverse is also prime? (For example, inverse ...
14
votes
2answers
397 views

Numbers that are divisible by the number of primes smaller than them

Let $\pi(n)$ denote the number of primes less than or equal to $n$ (a.k.a the prime-counting function). For certain values of $n$, the value of $\frac{n}{\pi(n)}$ is integer. Here are the first few ...
14
votes
2answers
1k views

sums of square free numbers , is this conjecture equivalent to goldbach's conjecture?

As one can notice every integer greater than $1$ is a sum of two squarefree numbers.(numbers that are not divided by some prime square power). Can we prove that? Edit: Can we have bounds for the ...
14
votes
3answers
438 views

If $p$ is a prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

The proof is already given in the textbook but I tried other way around. Proof by contradiction: Let's assume that $p$ doesn't divide $a$ and $p$ doesn't divide $b$, but $p$ divides $ab$. So ...
14
votes
2answers
1k views

Proof involving induction and primes

I'm looking to prove that: $$p_n \leq 2^{2^{n-1}}$$ Where $p_n$ denotes the $n$th prime in ascending order. The proof method is induction. I've solved my base case, that is: $n=1$ $p_1 = 2$, ...
14
votes
2answers
497 views

Primes sum ratio

Let $$G(n)=\begin{cases}1 &\text{if }n \text{ is a prime }\equiv 3\bmod17\\0&\text{otherwise}\end{cases}$$ And let $$P(n)=\begin{cases}1 &\text{if }n \text{ is a prime ...
14
votes
2answers
424 views

A conjecture concerning primes and algebra

A monoid morphism $\psi:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ is defined by an arbitrary function $f:\mathbb Z_+\!\!\rightarrow\mathbb Z_+$ and defines a group homomorphism $\varphi:\mathbb ...
14
votes
1answer
292 views

Prime pair points slope approaches 1

Take the list of primes, $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \ldots$$ and create ordered $(x,y)$ pairs by grouping in sequence, $$(2, 3), (5, 7), (11, 13), ...