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

2
votes
2answers
284 views

How to show that $n$ is a prime?

Suppose that $n>1$ satisfies $(n-1)! \equiv -1 \pmod n$. Show that $n$ is a prime. (Hint: Antithesis) My own trying: $n=3$: $(3-1)!+1= 3 \cdot 1$ => $3|2!+1$. $n=5$: $(5-1)!+1=25 = 5 \cdot 5$ ...
8
votes
3answers
1k views

How to show $p_n$ $\leq$ $2^{2^n}$?

Let $p_n$ be the $n_{th}$ prime (e.g. $p_1 = 2$; $p_2 = 3$; $p_3 = 5$). Show that $p_n \leq 2^{2^n}$ for all $n$. I don't see how I can approximate the value of $p_n$. Do I need something like ...
2
votes
1answer
220 views

If a prime with prime norm is a split prime, in the number ring PID

If a prime with prime norm is a split prime , in an number ring PID? Example: $5-\sqrt{14}$ in $\mathbb{Z}[\sqrt{14}]$ has norm $11$, it is a split prime in $\mathbb{Z}[\sqrt{14}]$? Why? Thanks
3
votes
1answer
315 views

Prime congruence

If $p\equiv3\pmod{4}$ and $q=2p+1$ is a prime then $q|(2^p-1)$ if $2^p-1$ is composite. Also, prove that there are infinitely many primes $p$ for which $2^p-1$ is composite.
9
votes
1answer
529 views

The largest possible prime gap?

What is the largest possible prime gap if we observe only 1000-digits numbers? There are few conjectures about this question but is there something that we can say and be absolutely sure of it?
4
votes
2answers
279 views

What's wrong with my proof of infinitely many primes of the form $am+b$, $\gcd(a, b) = 1$

So the prof said in class that the proof of this is hard, but we might want to attempt at home. I won't be able to see him again until Wednesday, but I'm guessing there is some hole in my proof, since ...
4
votes
1answer
252 views

How to find primes between $p$ and $p^2$ where $p$ is arbitrary prime number?

What is the most efficient algorithm for finding prime numbers which belongs to the interval $(p,p^2)$ , where $p$ is some arbitrary prime number? I have heard for Sieve of Atkin but is there some ...
28
votes
3answers
606 views

Sequence of numbers with prime factorization $pq^2$

I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions: What is the ...
5
votes
3answers
468 views

Powers as a complete residue system modulo $p$?

Question 1. With $0 < a < p$, $p$ prime and $\gcd(a,p-1)=1$, is it true that $0, 1, 2^a, ...,(p-1)^a$ is a complete residue system modulo $p$? If not, will a similar statement hold? Question ...
5
votes
3answers
372 views

Properties of Fermat primes

Fermat primes 17 and 257 appear a lot in the prime composition of numbers of the form $a^{2^n}+1$. For example, $11^8+1$ is divisible by 17 and $11^{32}+1$ is divisible by 257. I have verified the ...
1
vote
0answers
98 views

Infinite number of primes in the sequence $1+t^2$? [duplicate]

Possible Duplicate: Primes of the form $n^2+1$ - hard? $1, 2, 5, 10, 17, \ldots$ Are there an infinite number of primes in this sequence $1 + t^2$, $t$ being an integer?
2
votes
5answers
2k views

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$

Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$, where $n=0,1,2, \dots$
9
votes
2answers
237 views

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime?

Is there any number greater than 8 of the form $2^{2k+1}$ which is the sum of a prime and a safe prime? While answering @pedja's question about the existence of any such representations I was ...
6
votes
1answer
567 views

Are the primes found as a subset in this sequence $a_n$?

Below is a introduction that contains some background to my question. The question is found at the bottom. By calculating the eigenvalues of the matrix defined by the recurrence: $\displaystyle ...
4
votes
1answer
414 views

Even numbers greater than 10 as sum of two specific odd numbers

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved(or disproved) ,so my question is: Is it true that every even number ...
2
votes
1answer
837 views

Even numbers greater than 6 as sum of two specific primes

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved ,so my question is: Is it true that every even number greater than 6 ...
4
votes
5answers
26k 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 ...
21
votes
1answer
761 views

A continued fraction involving prime numbers

What is the limit of the continued fraction $$\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{5+\cfrac{1}{7+\cfrac{1}{11+\cfrac{1}{13+\cdots}}}}}}\ ?$$ Is the limit algebraic, or expressible in terms of e or ...
3
votes
2answers
421 views

A conjecture about the form of some prime numbers

Let $k$ be an odd number of the form $k=2p+1$ ,where $p$ denote any prime number, then it is true that for each number $k$ at least one of $6k-1$, $6k+1$ gives a prime number. Can someone prove or ...
12
votes
7answers
9k 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 ...
1
vote
1answer
132 views

Checking if all elements are prime

I've often come across problems where (as a subproblem) I need to decide whether a list of numbers contains only primes or at least one nonprime. Is there an efficient way to do this? Right now I ...
10
votes
5answers
257 views

Is there a single or best reason that 2 is an exceptional prime?

I've recently been studying some elementary number theory, and I've frequently come across the fact that there are a fair number of results (the main one being the law of quadratic reciprocity) for ...
3
votes
1answer
281 views

The Number of Prime Factors

x equals any whole number. y equals the number of prime factors of x. You plot those points, then find a line of best fit. What would the equation for that line be? Also; why? $x = 48$ $y = 5$ ...
10
votes
2answers
515 views

Smallest prime in arithmetic progressions: upper bounds?

This question is inspired by @Dan Brumleve's question on finding Pratt certificates efficiently. In a comment, I say that his problem is as hard as factoring, as long as the following problem is ...
6
votes
1answer
288 views

Can a Pratt certificate for a prime be found in polynomial time?

Can a Pratt certificate for a prime be found in polynomial time? I guess this is the same as asking whether the AKS primality test provides extra information that allows $p-1$ to be factored quickly. ...
13
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 ...
3
votes
2answers
483 views

When was the last prime number discovered? [closed]

By last, I mean the most recently discovered prime number. What was the length of time between the discovery of the last two prime numbers?
30
votes
2answers
692 views

Proof of no prime-representing polynomial in 2 variables

In "The New Book of Prime Number Records", Ribenboim reviews the known results on the degree and number of variables of prime-representing polynomials (those are polynomials such that the set of ...
7
votes
1answer
271 views

Prime spirals on surfaces of revolution

This is an entirely naive question, and in addition, vague. Apologies in advance! Imagine wrapping the Ulam prime spiral around a surface in $\mathbb{R}^3$, something like this: This suggests ...
5
votes
2answers
590 views

lower bound for the prime number function

Does there exist a function $f$ that is a lower bound of the prime number function $\pi$ with $f \sim \pi$?
2
votes
2answers
274 views

Set of prime numbers and subrings of the rationals

Let $P$ denote a set of prime numbers and let $R_{P}$ be the set of all rational numbers such that $p$ does not divides the denominator of elements of $R_{P}$ for every $p \in P$. If $R$ is a subring ...
4
votes
1answer
3k views

Understanding the Sieve of Atkin

I'm attempting to construct a program (in C++) that will count the prime factors of a given number for a Project Euler problem using the Sieve of Atkin, but I'm having trouble understanding a few ...
9
votes
1answer
271 views

primegaps w.r.t. the m first primes / jacobsthal's function

Maybe I don't see the obvious here; but well. I looked at an old discussion concerning prime gaps. I now tried to ask a somehow opposite way: Assume the set $\small P(m)$ of first m primes $\small ...
2
votes
4answers
533 views

Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it's proved?

Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it's proved? For example if $N = 20$: with $2$ we cross out: ...
2
votes
2answers
353 views

Checking safe primes

I am in need of a fast algorithm that checks if a given number is a safe prime.* Any help on this would be appreciated. *Definition: A safe prime is a prime number of the form $2p + 1$, where $p$ ...
3
votes
3answers
538 views

How to check if an integer has a prime number in it?

Is there any way by which one can check if an integer has a prime number as a subsequence (may be non-contiguous)? We can check if they contain the digits 2,3,5 or 7 by going through the digits, ...
9
votes
1answer
214 views

What might the (normalized) pair correlation function of prime numbers look like? [closed]

You might have read about the fortuitous meeting between Montgomery and Dyson. The background is that the nontrivial zeros of the Riemann zeta function, when normalized to have unit spacing on ...
3
votes
1answer
428 views

Matching coefficients of polynomial congruences

I was reading about the AKS Primality test when the following proof threw me off a bit. The following proof is given directly from the original paper Primes in P by Agrawal, Kayal and Saxena. Lemma ...
6
votes
3answers
165 views

Number of $k^p \bmod q$ classes when $q\%p > 1$

I want to show that when $p, q$ are primes, $k^p\bmod q$ takes on $q-1$ distinct values (as $k$ ranges over positive integers) if and only if $q \not\equiv 1 \pmod p$. (It is easy to verify this ...
9
votes
2answers
423 views

A limit involving prime numbers

Me and a friend of mine worked on building a problem for AMM. It all started pretty well, but in the end we realized that the initial part of the solution was wrong. In few words, we thought we have ...
9
votes
3answers
1k views

Cyclic numbers are characterized by the reciprocals of full reptend primes?

The number $142,857$ is widely known as a cyclic number, meaning consecutive multiples are cyclic permutations, i.e. $1 × 142,857 = 142,857$ $2 × 142,857 = 285,714$ $3 × 142,857 = ...
2
votes
1answer
98 views

Factoring short intervals

There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example, $(x^2,x^2+x)$ can be factored in time roughly linear in $x$. ...
6
votes
1answer
277 views

Asymptotics for prime sums of three consecutive primes

We consider the sequence $R_n=p_n+p_{n+1}+p_{n+2}$, where $\{p_i\}$ is the prime number sequence, with $p_0=2$, $p_1=3$, $p_2=5$, etc.. The first few values of $R_n$ for $n=0,1,2,\dots $ are: $10, ...
7
votes
2answers
916 views

Is it possible to prove that $3$ is a primitive root of any Fermat prime without quadratic reciprocity?

Browsing around online, I find a handful of proofs that $3$ is always a primitive root of any Fermat prime $2^n+1$. One particular proof is found in problems 4 and 5 here. Another proof I found on a ...
1
vote
1answer
115 views

When is an extension of a prime also a prime?

Suppose $R$ and $S$ are domains, $S$ is integral over $R$, $R$ is integrally closed, $p_1$ and $p_2$ are primes in the domain $R$, $p_1$ contains $p_2$, $q_1$ is a prime in the domain $S$ and lying ...
0
votes
3answers
363 views

Do there exist any dormant primes?

Suppose that n is an integer > 1 such that: The prime factorization of n is known It is known that (n + 1) is a prime Then: What can be concluded? Among the possibilities are the following: We ...
5
votes
1answer
224 views

Asymptotic behavior of $\sum_{i>0} x^{p_i}$ as $x \to 1^-$

The sum of natural numbers $ \sum_{n>0} x^n = \frac{x}{1-x}$, so as $x\to1^-$ it diverges as $(1-x)^{-1}$. So I wondered what would happen if we make the summation set thinner, i.e. $\sum_{n \in A} ...
3
votes
0answers
409 views

What does this say about prime numbers?

I was having fun with Sage when I noticed something interesting: ...
16
votes
2answers
709 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 ...
1
vote
0answers
92 views

Conjecture:$ \forall x , \exists m,n$, $ x<m<n $ and make $\pi(p_{m}+m) - m > \pi(p_{n}+n) - n$

$p_i$ is the $i^{\rm th}$ prime. $\pi(x)$ is prime counting function. Firstly, I think that Prime gap inequality holds true for any $i>0$: $p_{i+1} - p_{i} \leq i$. Very often, $\pi(p_{m}+m) - m ...