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
3answers
506 views

Patterns in Prime numbers, and the null hypothesis

I've read about many attempts to find patterns in prime numbers. First, is there a mathematical way to prove there is not a pattern to prime numbers? Since there are ways to check if a number is ...
12
votes
2answers
654 views

Ulam spiral: Is there an “unusual amount of clumping” in prime-rich quadratic polynomials?

I was reading Martin Gardner's Mathematical Games column on the Ulam spiral which appeared in the March 1964 issue of Scientific American. (The spiral actually featured on the cover of that issue.) ...
5
votes
2answers
481 views

Prime factors of $n^2+1$

I know it is unknown if there are infinitely many primes of the form $n^2+1$. Is it known if there is a positive integer $k$ such that $|\{n\in\mathbb{Z}:n^2+1 \text{ has at most k prime ...
1
vote
1answer
107 views

Dividing an interval, such that the primes get divided even

I have an interval $[2,t]$ containing some number of primes. I now want to divide this interval into two intervals $a=[2,m]$ and $b=]m,t]$ such that the number of primes in $a$ and $b$ is almost the ...
0
votes
1answer
310 views

Method to solving this proof with a java app

I'm writing a program to solve this proof, but I don't know how to go about solving it. If anyone has some insight it would be great help. Thanks For every odd integer $n$, $3 \leq n \leq 199$, ...
3
votes
2answers
273 views

Deterministic random numbers generator using $p^n \mod q$

I figured that I can create a deterministic "random" numbers generator by utilizing a bit of "magic" that I picked up from some cryptography. However I seem to have missed a detail. Basically the ...
1
vote
1answer
286 views

Invertibility of prime ideals in a number ring lying over prime numbers

I have trouble understanding an argument in the proof of the Kummer-Dedekind theorem. I am referring to a proof given in Peter Stevenhagen's notes. http://websites.math.leidenuniv.nl/algebra/ant.pdf ...
1
vote
2answers
1k views

What is the largest prime less than 2^31?

I'm sorry for this kind of specific question, I'd love if you could link to resources (prime lists, etc) that can answer similar questions more generically.
10
votes
4answers
2k views

How can one efficiently generate n small relatively prime integers?

The definition of small is that they have O(lg n) bits. One way is just to test the integers 2,3,... for primality and keep the first n primes, but this takes at least O(n log n) time (times the cost ...
7
votes
5answers
1k views

The least prime greater than 2000

I'm a bit curious as to how "real" mathematicians would solve this problem. "Find the least prime number greater than 2000." Of course, I can always go brute force: ...
4
votes
2answers
194 views

Bounds on prime number spacing

Suppose n is an integer. What kind of bounds do we know for how close the closest prime p > n will be? I'd especially appreciate an answer that pushes me in the right direction of proving a good ...
3
votes
2answers
598 views

How do you determine if a number is prime or composite?

Is there any way to decipher, manually of course, whether a (large enough) number is a prime?
2
votes
3answers
2k views

How to find next prime number?

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?
7
votes
3answers
584 views

When do the multiples of two primes span all large enough natural numbers?

It is well-known that given two primes $p$ and $q$, $pZ + qZ = Z$ where $Z$ stands for all integers. It seems to me that the set of natural number multiples, i.e. $pN + qN$ also span all natural ...
8
votes
3answers
595 views

An inverse for Euler's zeta function product formula

Of course, Euler proved that the Riemann zeta function can be defined as the analytic continuation of a product over all primes. $$\zeta(s) = \prod_{p \in \mathbb{P}}\frac1{1-p^{-s}}$$ It is well ...
2
votes
2answers
242 views

Solving $2x \equiv 1 \pmod{p}$ where $p$ is an odd prime

Solve $2x \equiv 1 \pmod{p}$ where $p$ is an odd prime. I'm really stuck on this one.
6
votes
2answers
300 views

A Question on RH relating to Prime Number theorem

Well, in a previous post regarding the explanation of Riemann Hypothesis Matt answered that: The prime number theorem states that the number of primes less than or equal to $x$ is approximately ...
7
votes
2answers
538 views

Accuracy of approximation to inclusion-exclusion formula in prime sieve

This thing came up in a combinatorics course I am taking. Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of ...
23
votes
2answers
10k views

Why are very large prime numbers important in cryptography?

Firstly, you guys are awesome, and I learn quite a bit just from reading the questions of others. Secondly, a friend asked me recently why large primes are important for data security, and I was ...
-4
votes
3answers
573 views

Sum of primes up to p is multiple of p?

Is the sum of primes up to p a multiple of p? i.e Is 1+2+...+p divisible by p and how would you prove it?
5
votes
1answer
524 views

Maximum order of integers coprime to a prime $p$

The following is a lemma I read online, but I don't understand part of the proof. Let $d$ be the maximum possible order among integers $a$ prime to $p$. Then for any integer $a$ not divisible by ...
0
votes
2answers
143 views

Conjecture about the set of Sphenic numbers

Sum of a set of sphenic numbers can't be equal to the sum of any other set of sphenic numbers. By that I meant, Say S is the set of sphenic numbers. Let S$_1$ $\subset$ S. Then there is no such ...
6
votes
3answers
941 views

Showing $x^8\equiv 16 \pmod{p}$ is solvable for all primes $p$

I'm still making my way along in Niven's Intro to Number Theory, and the title problem is giving me a little trouble near the end, and I was hoping someone could help get me through it. Now ...
5
votes
2answers
894 views

The Prime Polynomial : Generating Prime Numbers

First of all, i'll confess i'm no math geek. I'm from Stackoverflow, but this question seemed more apt here, so i decided to ask you guys :) Now, i know noone has discovered (or ever will) a ...
3
votes
4answers
947 views

Show that a number is not prime?

Show that for any integer $n>1$, all the numbers $n!+2, n!+3, \ldots, n!+n$ are composite (i.e. not prime).
2
votes
1answer
418 views

Finding probable primes with large numbers of digits

I have a homework assignment to find the two smallest probable primes with $12$ digits, where a probable prime is defined as a number such that $a^{p-1} \equiv 1\ (\textrm{mod}\ p)$, where $a = 2, 3, ...
5
votes
1answer
208 views

Partitioning sets such that the sum of 2 elements is Prime

Given an $n >0$ is it possible to partition the set $\mathcal{P} = \{1,2, \cdots, 2n\}$ into $n$ pairs $(a_{i},b_{i})$ such that $a_{i} + b_{i}$ is a prime?
0
votes
1answer
185 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$ ...
0
votes
3answers
530 views

Find x such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$)

Suppose you have two distinct large primes $p$ and $q$. Explain how you can find an integer $x$ such that $x^2 \equiv 49$ (mod $pq$), $x \not\equiv\pm 7$ (mod $pq$).
2
votes
1answer
581 views

Where can I find a list of sphenic numbers?

According to Wikipedia, A Sphenic number is a positive integer which >is the product of three distinct prime numbers. Anybody knows whether there is a list, say first 1000 sphenic numbers? It ...
2
votes
2answers
246 views

Prime divisibility

I have the following assertion in my notes from last year that I'm trying hard to digest, but I think it isn't true: If $p$ is prime $\Leftrightarrow$ if $p | ab$ then either $p | a$ or $p | b$ or ...
19
votes
6answers
4k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
5
votes
2answers
830 views

Generalizing values which Euler's-totient function does not take

I was reading about Euler's totient function on wikipedia, and it eventually led me to this book on google: Page 74 of the book, Prime numbers: the most mysterious figures in math By David G. Wells. ...
3
votes
1answer
424 views

Prime Number theorem and the prime counting function

Could someone please help me understand this proof given in an article by William Miller its supposed to follow from the prime number theorem that given, $A(x)$ which is the sum of all primes less ...
12
votes
6answers
11k 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?
11
votes
1answer
678 views

What's the probability that a sum of dice is prime?

Prompted by today's Minute Math question on the MAA site (http://amc.maa.org/mathclub/5-0,problems/T-problems/T-web,ia/2005web/tb05-12-ia.shtml), I started thinking about the probability that the sum ...
1
vote
2answers
854 views

Why do primes other than 2 and 5 divide infinitely many repunits?

I first noticed this is true for the integers of the sequence $9, 99, 999, 9999,\dots$, since for some term $a_n=10^n-1$ in the sequence and $p$ a prime other than $2$ or $5$, we have $a_n\equiv 0 ...
1
vote
1answer
525 views

If the order divides a prime P then the order is P (or 1)

I've just come up with this question as I'm studying for a number theory midterm. If $p$ and $q$ are different prime numbers, and it's known that $2^p \equiv 1 \bmod{q}$, then $q\equiv 1 \bmod{p}$. ...
15
votes
4answers
8k views

Simple explanation and examples of the Miller-Rabin Primality Test

Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test. Specifically: I understand that for some reason, having non-trivial ...
6
votes
1answer
1k views

Are there infinitely many primes of the form $4n^{2}+3$?

We, know that there are infinitely many primes of the form $4n-1,4n+1,5n-1,\cdots, \text{etc}$. I saw these things in Apostol's Introduction to Analytic Number theory textbook. I would like to have an ...
6
votes
2answers
418 views

Bijection between twin primes and numbers $n$ such that $n^2-1$ has exactly four positive divisors

I'm working my way through Niven's Introduction to Number Theory, and the wording of the following problem is making me unsure of my answer: Show that there is a one-to-one correspondence between ...
8
votes
1answer
239 views

How to show that all even perfect numbers are obtained via Mersenne primes?

A number $n$ is perfect if it's equal to the sum of its divisors (smaller than itself). A well known theorem by Euler states that every even perfect number is of the form $2^{p-1}(2^p-1)$ where ...
7
votes
4answers
1k views

Alternate definition of prime number

I know the definition of prime number when dealing with integers, but I can't understand why the following definition also works: A prime is a quantity $p$ such that whenever $p$ is a factor of ...
1
vote
2answers
314 views

Finding the Value of $\sum\limits_{n=1}^{p-1} [\sqrt{np} \ ]$

How does one find the value of the sum : $$\sum\limits_{n=1}^{p-1} [\sqrt{np} \ ]$$ where $p$ is a prime such that $p \equiv 1 (\text{mod} \ 4)$. If i remember correctly, i got this sometime back, ...
2
votes
2answers
148 views

Condition for Connectedness of Graph of Prime Numbers Differing in only $1$ Digit

(This question is inspired by the StackOverflow question Converting prime numbers by @Manas, which turns out to be the problem PPATH of SPOJ.) Let's construct a ...
51
votes
3answers
2k views

$5^n+n$ is never prime?

In the comments to the question: If $(a^{n}+n ) \mid (b^{n}+n)$ for all $n$, then $ a=b$, there was a claim that $5^n+n$ is never prime (for integer $n>0$). It does not look obvious to prove, nor ...
8
votes
1answer
444 views

Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $[a,b]$

Consider the closed interval $[0,1]$, there is $\frac{2}{3} \in [0,1]$ where $p=2$ and $q=3$. Similarly consider $[2,3]$, one can have $\frac{5}{2} \in [2,3]$ where $p=5$ and $q=2$. Does every ...
3
votes
1answer
833 views

Sum of divisors and prime numbers, short proof

Let $p_i$ denote the $i^{th}$ prime number. Find the smallest positive integer $k$ such that the product $n = p_1 \cdot p_2 \cdots p_k$ satisfies $\sigma(n) > 3n$. Is there any positive integer $m ...
16
votes
4answers
3k views

Is a prime number still a prime when in a different base?

Is a prime number in the decimal system still a prime when converted to a different base?
5
votes
1answer
1k views

On the binary decimal expansion of the reciprocal prime's

I have been thinking a little bit about the binary decimal expansion of reciprocal prime numbers; and I have a few questions. I found this neat table which lists the binary expansion of many ...