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

11
votes
5answers
2k 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 ...
-1
votes
3answers
581 views

Prime number rule

I was requesting somebody to help me discuss how the prime number rule helps to solve easily the sudoku game in just a few minutes and an example showing the relevant steps on how the rule is used
4
votes
2answers
674 views

Prove that an odd integer $n>1$ is prime if and only if it is not expressible as a sum of three or more consecutive integers.

Prove that an odd integer $n>1$ is prime if and only if it is not expressible as a sum of three or more consecutive integers. I can see how this works with various examples of the sum of three or ...
5
votes
2answers
392 views

No prime number between number and square of number

Find the values of $x \in \mathbb{Z}$ such that there is no prime number between $x$ and $x^2$. Is there any such number?
2
votes
2answers
1k views

Prime powers that divide a factorial [duplicate]

Possible Duplicate: How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes? If we have some prime $p$ and a natural number $k$, is there a formula ...
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 ...
16
votes
3answers
647 views

RSA in plain English

I'm a computer science student, I'm not a mathematician, I don't know anything about number or group theory. I'm looking at RSA, and I want to understand it. I know what Fermats's little theorem and ...
8
votes
4answers
921 views

How many consecutive composite integers follow k!+1?

I wrote a program for myself in Mathematica to generate the answer for the first 300, which was really easy, but I can't find a pattern. The results are here. This is a problem in Underwood Dudley's ...
6
votes
5answers
2k views

If $2^{n+1} - 1$ is composite, is $2^{n+2} - 1$ prime?

In 1556, Tartaglia claimed that the sums 1 + 2 + 4 1 + 2 + 4 + 8 1 + 2 + 4 + 8 + 16 are alternative prime and composite. Show that his conjecture is false. With a simple counter example, $1 + 2 ...
9
votes
1answer
386 views

The set of rational numbers of the form p/p', where p and p' are prime, is dense in $[0, \infty)$

I have been working through the exercises in Tenenbaum's "Introduction to analytic and probabilistic number theory" book, and I am stumped here (Exercise I.1.6). This is not a homework assignment, ...
0
votes
1answer
135 views

Gruenberger's prime path

hi i'm looking for some historical informations about Gruenberger path. it is a path based on conjecture that every prime could be written in the form $6k+1$ and $6k-1$ (but what is the name of this ...
8
votes
2answers
1k views

prime numbers in Pascal's triangle

Just wondering about this: Is it true that there are no prime numbers in Pascal's triangle, with the exception of $\binom{n}{1}$ and $\binom{n}{n-1}$? From the first 18 lines it appears that this is ...
1
vote
2answers
177 views

calculate $a^{(P-1)/2}\pmod{P}$ for large prime

How can I calculate $a^{(P-1)/2}\pmod{P}$? for example $3^{500001}\bmod{1000003}$ given that $1000003$ is prime. I know that if we square the number $3^{500001}$ the result will be either $1$ or ...
5
votes
1answer
247 views

Are there other pseudo-random distributions like the prime-numbers?

Does there exists other structures in math, which are seemingly random, but deterministic, and follow rules similar to the prime numbers, by rules I mean there must be statements similar to goldbach's ...
1
vote
1answer
291 views

arithmetic progression of primes

Prove that there is no arithmetic progression that consists only of primes. A question that I've been set; I'm guessing it makes use of primes being written in the form 4k+1 and 4k+3? Not sure where ...
3
votes
2answers
415 views

Constructible Polygon and Fermat's Prime

I came across this puzzle at some online contest(now completed) Alexander, son of Phillip of Macedon, has ascended the throne of his father following his assassination. In these tumultuous times, ...
15
votes
2answers
781 views

A Conjecture of Schinzel and Sierpinski

Melvyn Nathanson, in his book Methods in Number Theory (Chapter 8: Prime Number's) states the following: A conjecture of Schinzel and Sierpinski asserts that every positive rational number $x$ can ...
14
votes
1answer
412 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 ...
6
votes
1answer
1k views

One line Proof of the Prime Number Theorem

Whenever I am not doing anything, I generally happen to see pages of some good Mathematical Institutes in India, so as to know more about the faculty members and see what they are working on. While ...
0
votes
2answers
319 views

Detecting if a decimal is terminal or not?

If $x$ is prime and $1000000000000 < x < 1000100000000$, how can I detect if $1 / x$ will result in a terminal decimal or not? I can use programming.
2
votes
1answer
303 views
4
votes
2answers
521 views

Show for prime numbers of the form $p=4n+1$, $x=(2n)!$ solves the congruence $x^2\equiv-1 \pmod p$. $p$ is therefore not a gaussian prime.

I need to show that for prime numbers of the form $p=4n+1$, $x=(2n)!$ solves the congruence $x^2 \equiv-1\pmod p$. I then need to show this implies p isn't a gaussian prime. I have started to solve ...
6
votes
2answers
699 views

Does the sum of reciprocals of primes converge?

Is this series known to converge, and if so, what does it converge to (if known)? Where $p_n$ is prime number n, and $p_1 = 2$, $$\sum\limits_{n=1}^{\infty} \frac{1}{p_n}$$
22
votes
3answers
1k views

Show that product of primes, $\prod_{k=1}^{\pi(n)} p_k < 4^n$

This an interesting problem my friend has been working on for a while now (I just saw it an hour ago, but could not come up with anything substantial besides some PMI attempts). Here's the full ...
34
votes
2answers
1k views

Prime powers, patterns similar to $\lbrace 0,1,0,2,0,1,0,3\ldots \rbrace$ and formulas for $\sigma_k(n)$

Some time ago when decomponsing the natural numbers, $\mathbb{N}$, in prime powes I noticed a pattern in their powers. Taking, for example, the numbers $\lbrace 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
26
votes
2answers
824 views

Elementary proof that $2x^2+xy+3y^2$ represents infinitely many primes?

We did in class $x^2+y^2$, which was easy, and we had for homework $2x^2+2xy+3y^2$, which I did (its values (if not square) must be divisible by form primes, or of the form $x^2+5y^2$, and clearly ...
6
votes
4answers
457 views

Algorithm for constructing primes

Are there any good algorithms which can be used to construct a prime greater than $n$, for arbitrary $n$? There are some brute force approaches: for example, factoring $n!+1$. However, I'm looking ...
4
votes
1answer
198 views

Prepending strings and primes?

we all know that 31,331,3331,33331,333331,3333331,33333331 all are primes. Here we prepend the digit 3 to 31, to get a list of 7 primes.This gives me the following thought: Let $D = \{\text{all ...
7
votes
2answers
444 views

Highly composite number

Definition: n is said to be a highly composite number if and only if $d(n)>d(m)$ for all $m<n$, where $d(n)$ denotes number of divisors of n. Questions: 1) Are there any theorems about highest ...
12
votes
1answer
966 views

Twin, cousin, sexy, … primes

Twin, cousin, and sexy primes are of the forms $(p,p+2)$, $(p,p+4)$, $(p,p+6)$ respectively, for $p$ a prime. The Wikipedia article on cousin primes says that, "It follows from the first ...
5
votes
1answer
172 views

trajectories in ListPlot[the maximal prime factor of average of twin prime pair]

another sequence on twin primes The maximal prime factor of average of twin prime pair: n = 100000; averageList = Select[Prime[Range[n]], PrimeQ[# + 2] &] + 1; mpfList = FactorInteger[#][[-1, 1]] ...
2
votes
2answers
81 views

numbers interference

a sequence on twin primes In the diagram, How do the stripes come from? Can the prime numbers also interfere like light and wave? When zoom in or zoom out the diagram in Mathematica, the stripes are ...
2
votes
1answer
1k views
4
votes
1answer
1k views

Factoring large integers without a cluster

What is the best program to factor large arbitrary-form integers on a single computer, or on a few disjointed computers? "Best" is obviously subjective, but what do you recommend? I'm working on a ...
7
votes
3answers
280 views

What is the maximum number of primes generated consecutively generated by a polynomial of degree $a$?

Let $p(n)$ be a polynomial of degree $a$. Start of with plunging in arguments from zero and go up one integer at the time. Go on until you have come at an integer argument $n$ of which $p(n)$'s value ...
3
votes
2answers
474 views

Miller-Rabin Primality Testing failure and a subgroup

Let $n$ be composite. I'm trying to figure out if the set $H$ of $a$ such that 1) $a$ is relatively prime to $n$ and 2) the Miller-Rabin test fails to show compositeness of $n$ with $a$ is a ...
3
votes
2answers
127 views

When $a$ and $b$ are co-prime, is $F(x) = a x \mod b$, $x$ in $[0,b)$ , $a$ and $b$ co-prime, an injective function?

I'm trying to figure out whether my hardware function for mapping operating system pages to DDR memory controllers is injective: $$F(x) = a x \pmod{b},\text{ where $x$ in $[0,b)$, $a$ and $b$ are ...
1
vote
2answers
432 views

The highest power of a prime that divides $f(x)$

I have read a result on computing the highest power of a prime that divides $n!$. I was wondering if there are any results on how to compute the highest power of a prime dividing $f(x)$, where $f$ is ...
3
votes
6answers
525 views

Is there a rational number (with denominator not greater than 200) between 15/106 and 16/113?

Is there a rational number (with denominator not greater than 200) between 15/106 and 16/113?
8
votes
3answers
624 views

Dirichlet's theorem on primes in arithmetic progression

Is there a proof in the spirit of Euclid to prove Dirichlet's theorem on primes in arithmetic progression? (By the spirit of Euclid, I mean assuming finite number of primes we try to construct another ...
4
votes
3answers
1k views

Fermat's Christmas theorem on sums of two squares with Gaussian integers

Gaussian integers are the set: $$\mathbb{Z}[\imath] =\{a+b\imath : a,b \in\mathbb{Z} \}$$ With norm: $$\mathrm{N}(a+b\imath)=a^{2}+b^{2}.$$ It satisfies $\mathrm{N}(\alpha\cdot \beta ...
1
vote
3answers
519 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
684 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
523 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
324 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
3answers
286 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
324 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 ...