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

6
votes
2answers
175 views

Speeding through the primes until they look uniform

Imagine you are traveling out the $x$-axis such that your velocity at $x$ is $v(x)$. If $v(x)=1$, then you pass the primes at increasingly longer intervals, on average (of course there are close ...
2
votes
2answers
105 views

Proof that the first reappearing remainder when dividing one by a prime number is one

I am trying to proof that the first reappearing remainder when dividing one by a prime number is one. What I found is that if the expansion of $1/p$ recurs with period $k$ then $10^k-1$ is divisible ...
5
votes
3answers
222 views

If a prime $p$ satisfies given condition then $p^{4} \mid ap-b$

Question If $p > 3$ is a prime and $$ 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p} = \frac{a}{b}$$ then prove that $p^{4} \mid (ap-b)$. There is an exercise in Herstein which states, if $p > ...
2
votes
3answers
128 views

Finding a (small) prime great enough that there are at least m elements of order m

I'm hoping that someone can provide me with some results or point me in the right direction. I'm working with finite fields; really, I'm just doing arithmetic modulo a prime $p$. I'm taking elements ...
0
votes
2answers
439 views

Estimate the average number of prime factors of a 1000-digit number

More formally, find an asymptotic for $N\to\infty$ of $$\frac{\sum_{1\le k\le N} M(k)}{N}$$ where $$M(p_1^{d_1}p_2^{d_2}\cdots p_k^{d_k}) = d_1+d_2+\cdots+d_k$$ For example, $M(24) = M(2^3\cdot3) = ...
16
votes
4answers
3k views

Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

This question relates to a discussion on another message board. Euclid's proof of the infinitude of primes is an indirect proof (a.k.a. proof by contradiction, reductio ad absurdum, modus tollens). My ...
0
votes
1answer
149 views

Compositions of prime numbers

This question is related to numbers found in the OEIS sequence A191837. In this sequence, $a(2) = 48 = 5 + 7 + 17 + 19$, where the summands of 48 are all prime numbers that are less than or equal to ...
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.
1
vote
3answers
262 views

Is there a Non-prime Number that is Divisible only by Numbers Greater than its Square Root? [duplicate]

Possible Duplicate: Calculating prime numbers The question is in the title. Is there a number that is divisible only by numbers greater than its square root? If not, why? I need this ...
7
votes
1answer
635 views

Finding the 10001th Prime

I'm helping my son with Project Euler and we're working on problem 7, "What is the 10001st prime number?" We'll use a Sieve of Eratosthenes and we'll increase the size of the initial array until ...
0
votes
2answers
67 views

How to get a number into the form of $p^{s} \times n$?

In an article about the Miller-Rabin primality test, in the example section it says: "Suppose we wish to determine if $n = 221$ is prime. We write $n − 1 = 220$ as $2^{2}\times 55$, so that we have ...
1
vote
1answer
359 views

Algorithm for partitioning n into distinct primes

I am looking for an algorithm that will partition a positive integer into distinct primes. The number of partitions is given by this OEIS sequence: https://oeis.org/A000586 To be more specific, I am ...
1
vote
1answer
160 views

Why does $q \equiv (r-1)/2 \mod r$ mean that $2q \equiv -1 \mod r$?

In the paper Safe Prime Generation with a Combined Sieve by Michael J. Wiener, the author states: For any small odd prime $r$, we can eliminate candidates for $q$ that are congruent to $(r − ...
1
vote
2answers
725 views

Non repeating random number generation with x(i+1) = x(i) + increment mod m

I have to generate millions of non-repeating random numbers and came across this equation: $x_{i+1} = x_i+c \space(mod \ m)$, where c and m are relative primes and $m \geq total\ to\ be\ generated$. ...
8
votes
2answers
576 views

Can insight be derived from direct formulae for prime number functions?

Dear StackExchange Community, I am an amateur enthusiast and was attempting to construct a formula for the n th prime using elementary functions - I didn't achieve this* but I did come up with some ...
2
votes
1answer
229 views

How many safe primes are there?

Compared to the number of integers and the number of primes, how many safe primes are there? Specifically, I'd like to be able to estimate how many safe primes there are below a given number.
2
votes
2answers
206 views

Manipulating exponents of prime factorizations

Has work been done on looking at what happens to the exponents of the prime factorization of a number $n$ as compared to $n+1$? I am looking for published material or otherwise. For example, let ...
5
votes
1answer
284 views

Are there infinitely many primes next to smooth numbers?

A side discussion over on this question has left me curious: is there any $B$ for which it's known that there are infinitely many primes adjacent to $B$-smooth numbers (i.e., for which there are ...
8
votes
1answer
309 views

what is the name of this number? is it transcendental?

Consider the number with binary or decimal expansion 0.011010100010100010100... that is, the $n$'th entry is $1$ iff $n$ is prime and zero else. This number is ...
3
votes
1answer
239 views

A Quest of Legendre Theorem

I had came across a theorem a few weeks ago and I tried to make sense of it but could not at the time, so I put it down and recently picked it back up to take another shot, but the thing is, what I ...
3
votes
4answers
229 views

Can a number have a prime factor that isn't a part of the number's prime factorization?

Is it possible to have a number, $x$, divisible by some prime, such that that prime does not appear in the unique prime factorization of $x$?
3
votes
1answer
128 views

Find a finite extension of $\mathbb{Q}$ in which all primes split

Dear all, I would be grateful if someone could provide a solution to the following problem (using decomposition and inertia groups): Find a finite extension of $\mathbb{Q}$ in which all primes split. ...
7
votes
2answers
231 views

Given $2$ randomly chosen integers $x,y$ what is $P(k=gcd(x,y))$?

Given $2$ randomly chosen integers $x,y$ what is the probability that a integer $k$ is the greatest common divisor of $x$ and $y$? I know that the probability of $x,y$ being coprime is ...
14
votes
1answer
408 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 ...
1
vote
2answers
149 views

Another prime inquiry: how many primes from 1 to *k*?

With the question I made about primes, I noticed people enjoy the subject, so here's another thought: let k be a positive integer; how many primes are there from 1 to k? There's probably no exact ...
6
votes
4answers
328 views

Prime Appearances in Fibonacci Number Factorizations

Okay, THIS one is considerably more analytical... :P (Used my post here as a basis.) When successive Fibonacci numbers are factored, the primes appear in a specific order, which goes $2, 3, 5, 13, 7, ...
13
votes
1answer
723 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 ...
2
votes
0answers
154 views

$n$ by $n$ Primally Magic Squares

(Again copied verbatim from a September 2009 thread I made.) A Primally Magic Square (PMS) is exactly like a traditional magic square with a change of criteria. Where a traditional magic square is ...
6
votes
5answers
658 views

Can this number theory MCQ be solved in 4 minutes?

The Problem: ( 270 + 370 ) is divisible by which number? [ 5, 13, 11 , 7 ] Using Fermat's little theorem it took more than the double of the indicated time limit. But I would like to solve it quickly ...
4
votes
2answers
184 views

Are there distinct primes $p,q$ satisfying $pq=(2^r-1)(p+q)-5$?

We let $p\neq q$ be odd prime numbers and $r$ be integer $>2$. Are there such $p,q$ satisfying $pq=(2^r-1)(p+q)-5$? This is clear from here that, $q(p-2^r+1)=(2^r-1)p-5$, and ...
18
votes
3answers
1k views

Prime numbers stretch to infinity, but what about the distance between them?

That is, let $p_n$ be the nth positive prime number. Does $$L = \lim\limits_{n \to \infty} \left( p_{n+1} - p_n \right)$$ equal infinity?
2
votes
3answers
946 views

About the factors of the product of prime numbers

If a number is a product of unique prime numbers, are the factors of this number the used unique prime numbers ONLY? Example: 6 = 2 x 3, 15 = 3 x 5. But I don't know for large numbers. I will be using ...
6
votes
2answers
588 views

Infinite Prime Proof Using Euler's Totient

I need something explained or corrected: In my number theory class we proved that there are an infinite number of primes using Euler's Phi Totient. It went something like this: Let $M = p_1 p_2 ...
3
votes
2answers
315 views

Calculating prime numbers

I have a program which determines if a number is prime or not. The basic algorithm simply checks for the number being divisible by 1 and itself. My question is, is there an upper limit to checking ...
2
votes
3answers
308 views

RSA: Encrypting values bigger than the module

Good morning! This may be a stupid one, but still, I couldn't google the answer, so please consider answering it in 5 seconds and gaining a piece of rep :-) I'm not doing well with mathematics, and ...
12
votes
1answer
723 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 ...
3
votes
2answers
227 views

All primes $p,q,r$ such that $(p-q)^2+1=r$

How can one find all prime numbers $p,q,$ and $r$ such that $$(p-q)^2+1=r\ ?$$
5
votes
2answers
700 views

Euler's phi function and distinct primes

It is true that $\phi(p) = (p-1)$ only if p is a prime. I had also proven (I am not sure if this is a trivial fact or not) that $\phi(pq) = (p-1)(q-1)$ only if p and q are distinct primes. However, I ...
2
votes
1answer
55 views

Is there a generalisation of the distribution ratio

From the theory of numbers we have the Proposition: If $\mathfrak{a}$ and $\mathfrak{b}$ are mutually prime, then the density of primes congruent to $\mathfrak{b}$ modulo $\mathfrak{a}$ in ...
2
votes
1answer
199 views

How fast can we find primes (number of computations needed+time for the computation too)

So, I know we can get a bound on how long it will take to find a large prime. For example, using the fact that between $N$ and $2N$ there must be a prime. And the fact that all numbers between are ...
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 ...
9
votes
1answer
306 views

Sum of cosines of primes

Let $p_n$ be the nth prime number, $p_1=2,p_2=3,p_3=5,\ldots$ How to prove this series converges/diverges? $$\sum_{n=1}^\infty \cos{p_n}$$
7
votes
3answers
207 views

Combinatorics question: Show divisibility

Let $a\geq2$, $b\geq2$ be two prime numbers and k be a natural number with $k\leq min(a,b)$. How can one show that $z := \binom{a+b}{k} - \binom{a}{k} - \binom{b}{k}$ is divisible by the product ...
3
votes
3answers
279 views

bound of the number of the primes on an interval of length n

I made this observation and it seems reasonable to me to ask :if $n$ is a natural number then the number of the primes less than or equal to $n$ is denoted by $π(n)$ . is that true that in any ...
4
votes
1answer
104 views

Partitioning polynomials in $\mathbb{Z}[x,y]$ by the primes they represent

Suppose you have a set $S\subset\mathbb{Z}[x,y].$ How can one efficiently partition the polynomials into sets such that the primes represented by the polynomials in any given set are identical? For ...
5
votes
1answer
309 views

Square-free zeta function zeros

It is a well known fact that the geometric series $$1+x+x^2+x^3+\ldots$$ has the following form $$\frac{1}{1-x}$$ Another possible representation is $$\prod_{k=0}^{\infty}\left(1+x^{2^{k}}\right)$$ ...
6
votes
2answers
365 views

Relative density of primes under extension

Let $\mathbb{P}_{\mathbb{C}}$ be the set of Gaussian primes and $\mathbb{P}_{\mathbb{N}}$ the set of primes in $\mathbb{N}$. Let $\pi_{\mathbf{C}}(\sqrt{n})$ be the number of Gaussian primes with ...
1
vote
2answers
104 views

Estimating the Primarithm

Let's define the primarithm function, $pog : \mathbb{N} \rightarrow \mathbb{N}$, where $pog(n)$ is the largest number of distinct primes that can divide a natural number $k$, $k \leq n$. Does this ...
4
votes
3answers
624 views

What set of $10$-digit numbers with $k$ prime factors has largest cardinality?

Suppose $s_{1}$ are the numbers with 10-digits that have $1$ prime factor. Suppose $s_{2}$ are the numbers with 10-digits that have $2$ prime factors. Suppose $s_{n}$ are the numbers with 10-digits ...
1
vote
1answer
162 views

Proof of Primality Testing

I am learning some Cryptography and I came across this exercise where I have to make the following proof (translated from German, so I hope it is accurate). Proof the following assertion: Let $n ...