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

5
votes
0answers
264 views

Partial summation of a harmonic prime square series (Prime zeta functions)

I am trying to find the following series: $S=\displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\dfrac{1}{p_ip_j},A\leq p_1 < p_2 < \dots < p_n \leq B, \lbrace A,B\rbrace \in \mathbb{N}$ ...
2
votes
1answer
99 views

Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval: $\{318, 921, 1526, ...
1
vote
1answer
476 views

Modular Multiplicative Inverse & Modular Exponentiation Equation

I was solving a problem containing that equation. $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given: $1 \le a \le 2,000,000,000$ $0 \le n \le 2,000,000,000$ $2 \le m \le 2,000,000,000$ $a$ and $m$ ...
5
votes
1answer
222 views

Proving there are infinitely many primes of the form $a2^k+1.$

Fix $k \in \mathbb{Z}_+$. Prove that we can find infinitely many primes of the form $a2^k +1,$ where $a$ is a positive integer. We can use the result that: If $p \ne 2$ is a prime, and if ...
2
votes
1answer
81 views

Criterion for Wolstenholme Primes

Wolstenholme Theorem is a nice theorem that states that every prime $p >3$ satisfies: $$\binom{2p}{p} \equiv 2 \pmod {p^3}$$ A Wolstenholme prime is a prime $p$ such that $\binom{2p}{p} \equiv 2 ...
2
votes
1answer
2k views

Why choose a prime number as the number of slots for hashing function that uses divison method?

The division method is one way to create hash functions. The functions take the form: h(k) = k mod m Where k is a key and m is the number of slots Edit: If this is my hash function why should ...
7
votes
1answer
78 views

Parameters giving maximal-length Collatz-like sequence

In a recent question the following recursive sequence was considered: $$ a_{n+1} = \cases{\frac{a_n}{2} & $a_n$ is even \\ a_n +d & $a_n$ is odd}, \quad a_1 = d + 1 $$ where $d$ is an odd ...
14
votes
1answer
2k 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 ...
9
votes
4answers
353 views

Two problems with prime numbers

Problem 1. Prove that there exists $n\in\mathbb{N}$ such that in interval $(n^2, \ (n+1)^2)$ there are at least $1000$ prime numbers. Problem 2. Let $s_n=p_1+p_2+...+p_n$ where $p_i$ is the ...
3
votes
1answer
148 views

Solving a pair of congruences

Any ideas on how to solve the congruences \begin{eqnarray*} p^k &\equiv& 1 \mod q \\ q &\equiv& 1 \mod p \end{eqnarray*} where $p$ and $q$ are primes and $k$ is a ...
3
votes
4answers
251 views

Prime factorization, Composite integers.

Describe how to find a prime factor of 1742399 using at most 441 integer divisions and one square root. So far I have only square rooted 1742399 to get 1319.9996. I have also tried to find a prime ...
1
vote
1answer
154 views

Product of all primes less then x

How to prove that $\prod_{p\leqslant{x}}p\leqslant4^{x-1},\ \forall x\geqslant2$, where product is taken over all prime numbers $p\leqslant{x}$
2
votes
2answers
177 views

Matrices with elements that are a distinct set of prime numbers: always invertible?

Inspired by a previous question, given a square non-symmetric matrix whose elements are all prime but distinct from each other, does this guarantee that the matrix is invertible? It's easy to see ...
3
votes
1answer
209 views

Frequency of twin primes

Is there a function that gives the frequency with which twin primes less than a particular number, N (assuming N is not a part of a twin prime) occur? I've tried with a program but I did not notice ...
3
votes
1answer
172 views

Additive primes

The product of two integers is always an integer. However, the quotient of two integers is not always an integer. This simple fact leads directly to concepts such as "divisibility", "divisors" and ...
3
votes
2answers
201 views

Prime Identification easier than Prime Factorization?

I need an algorithm to decide quickly in the worst case if a 20 digit integer is prime or composite. I do not need the factors. Is the fastest way still a prime factorization algorithm? Or is there ...
0
votes
0answers
56 views

Riemann Siegel formula modification?

$$Z(t)= \sum_{n=1}^{\lfloor\sqrt t/2\pi\rfloor }\frac{\cos(N(t)-t\log p_{n})}{\sqrt n}$$ here $N(t)$ is the smooth part of the zeros and $ p_{n} $ are the primes since $ p_{n} =n\log n $ then $ \log ...
1
vote
2answers
87 views

Does this sequence have this interesting property relating to the prime factorization of the index?

Define a sequence as $a_0 = 0$ and $a_n$ equals the number of divisors of $n$ (including 1 and $n$) that are greater than $a_{n-1}$. This is sequence A152188 in OEIS, by the way. (For example, the ...
2
votes
1answer
123 views

Can we descend field extensions of prime degree of number fields to number fields of the same degree

Let $K$ be a number field and let $p$ be a prime number. Let $L$ be a degree $p$ field extension of $K$. Does there exist a degree $p$ field extension $M$ of $\mathbf{Q}$ such that ...
15
votes
1answer
363 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: ...
0
votes
2answers
132 views

$k$ hands in $n$'s hair

Moderator Message: this question is from an ongoing competition. Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands ...
3
votes
2answers
238 views

Is the set of dyadic rationals a field?

I recently learned that the dyadic rationals is the set of rational numbers of the form $$\frac{p}{2^q}$$ where $p$ is an integer and $q$ is greater than or equal to zero. I think the set of dyadic ...
26
votes
1answer
1k views

A prime number pattern

The algorithm Given a natural number $n$ define a procedure as follows: Generate a list of primes upto and possibly including, $n$ Assign $Z = n$ If $Z > 0$, subtract the largest prime from list ...
3
votes
1answer
106 views

Upper bound on smallest prime $p$ needed to tell two numbers $\leq n$ apart modulo $p$

I'm going through this paper: E. D. Demaine, S. Eisenstat, J. Shallit, and D. A. Wilson. Remarks on separating words. ArXiv e-prints, March 2011. And on page 2, there is the following lemma: Lemma ...
0
votes
3answers
213 views

If $p$ is a factor of $m^2$ then $p$ is a factor of $m$

I'm a complete beginner and not sure where to go with this proof of Euclid's lemma. Any help would be greatly appreciated. If $m$ is a positive integer and a prime number $p$ is a factor of $m^2,$ ...
1
vote
1answer
102 views

Prime-base products: Plot

For each $n \in \mathbb{N}$, let $f(n)$ map $n$ to the product of the primes that divide $n$. So for $n=112$, $n=2^4 \cdot 7^1$, $f(n)= 2 \cdot 7 = 14$. For $n=1000 = 2^3 \cdot 3^3$, $f(1000)=6$. ...
5
votes
4answers
1k views

The longest sum of consecutive primes that add to a prime less than 1,000,000

In Project Euler problem $50,$ the goal is to find the longest sum of consecutive primes that add to a prime less than $1,000,000. $ I have an efficient algorithm to generate a set of primes ...
5
votes
1answer
163 views

P[random x is composite | $2^{x-1}$ mod $x = 1$ ]?

Select a uniformly random integer $n$ between $2^{1024}$ and $2^{1025}$ (Q) What is the probability that n is composite given that $2^{n-1}$ mod $n = 1$ ? How did you calculate this? More info: ...
1
vote
1answer
309 views

Convergence of a series of reciprocal prime numbers

If $p$ is a prime number, and $q$ is its twin prime, the sum of the reciprocal twin numbers is convergent and the value of the sum of the series is the Brun constant. Now, if we consider the prime ...
3
votes
2answers
378 views

Any Practical Application for Prime Other Than Cryptography? [duplicate]

Possible Duplicate: Real world applications of prime numbers? Is there any practical application (I mean outside mathematics) for prime numbers other than cryptography?
7
votes
3answers
205 views

Generating random numbers with the distribution of the primes

I would like to generate random numbers whose distribution mimics that of the primes. So the number of generated random numbers less than $n$ should grow like $n / \log n$, most intervals ...
3
votes
3answers
233 views

Prove or disprove $\lim\limits_{n \to \infty} (p_{n+1} - p_{n})/\sqrt{p_n} = 0$

Can anyone prove or disprove the following statement? $$ \lim_{n \to \infty} \frac{p_{n+1} - p_{n}}{\sqrt{p_n}} = 0.$$
1
vote
1answer
115 views

Logarithms and prime factors

Let a-f be integers g.t. 2 with $a < b < c < d < e < f$. Let $$\ln def - \ln a b c = \alpha.$$ Let $\{p_i\}$ be the set of prime factors (with repetitions) in a,b,c. Let $\{q_i\}$ be ...
7
votes
1answer
1k views

Even numbers have more factors than odd numbers…

This was an exercise to show that, in a sense, the even numbers have more prime factors than the odds, but--if it's right-- I still have a question. As an heuristic calculation, we could take a large ...
4
votes
3answers
506 views

Relationship between prime factorizations of $n$ and $n+1$?

Are there any theorems that give us any information about the prime factorization of some integer $n+1$, if we already know the factorization of $n$? Recalling Euclid's famous proof for the infinity ...
1
vote
4answers
156 views

Equation involving prime numbers

Given the equation: $$p^2+\phi=q$$ where $p$ and $q$ are prime numbers and $\phi$ a constant, it seems the equation doesn't have solutions for $\phi=1,2,3$, but it has solutions for $\phi=4$. Is it ...
8
votes
2answers
349 views

Are there any elegant methods to classify of the Gaussian primes?

Out of curiosity, are there any relatively quick classifications of all the Gaussian primes, the primes in $\mathbb{Z}[i]$? I found a classification here, but the process comes off as rather tedious. ...
1
vote
0answers
151 views

factoring very very big random “numbers”

This is a variation on the theme of a rather flawed question that I asked months ago. Imagine a doubly infinite sequence, i.e. each member has a successor and a predecessor. Grab one term of the ...
1
vote
3answers
281 views

How to prove $p$ divides $a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}$ when $p$ is prime, $a, b \in \mathbb{Z}$ and $a,b \lt p$?

If $p$ is a prime number and $a, b \in \mathbb{Z}$ such that $a,b \lt p$, then how could we prove that $p$ divides $\left(a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}\right)$?
1
vote
2answers
302 views

Approximating next prime number

Suppose that there is a prime number. Now I want to approximate the next prime number. (It does not have to be exact.) What would be the time-efficient way to do this? Edit: what happens if we limit ...
3
votes
2answers
128 views

Why is the probability that a prime p is a factor of a number n equal to 1/p

I'm learning some number theory and I can't seem to understand why this is the case.
2
votes
0answers
82 views

asymtotic ratio of nonsquarefree repunits

Let $R_n:=\frac{10^n-1}{10-1}$ (called a repunit) and $\mu$ be the Moebius function. Also $[n]:=\{1,2,3,\cdots, n\}, A_n:=\{m \in [n]| \mu (R_m)=0\}.$ What is the value of $\lim \limits_{n ...
5
votes
2answers
311 views

Polynomials representing primes

Suppose over $\mathbb{Z}$ we are given an irreducible polynomial $p(x)$. Can we say that $p(x)$ at least represents a prime as $x$ runs through integers? Thanks in advance
1
vote
1answer
160 views

Two Representations of $\log \zeta$

I was looking for representations of $\log \zeta$ and found these two: $ \displaystyle \log\zeta(s)=\color{red}{s}\sum_{n>0} \frac{P(ns)}{n\color{red}{s}}$ from here [$\color{red}{s}$ inserted ...
4
votes
0answers
514 views

Obtain a contradiction

Motivation : The motivation is to show that the equation $x^{2b}.x^{2a} +(3-x^{2b}) x^{a} + (1-s^2)=0 $ has no solutions in integers for any values of $x,b,a,s$ ( choosen as per the constraints ...
13
votes
1answer
365 views

Prime spiral distribution into quadrants

Is it known that the primes on the Ulam prime spiral distribute themselves equally in sectors around the origin? To be specific, say the quadrants? (Each quadrant is closed on one axis and open on ...
8
votes
2answers
233 views

Generalized PNT in limit as numbers get large

If $\pi_k(n)$ is the cardinality of numbers with k prime factors (repetitions included) less than or equal n, the generalized Prime Number Theorem (GPNT) is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln ...
2
votes
1answer
485 views

Explain Carmichael's Function To A Novice

I understand that the Carmichael Function (I'm going to call C()) is essentially the smallest positive integer m, where $a^m$ is congruent $1 \pmod n$ for all co-primes less than n. 6 makes sense to ...
1
vote
0answers
63 views

How are prime numbers used to facilitate modern encryption? [duplicate]

Possible Duplicate: Why are very large prime numbers important in cryptography? I'm interested in how the algorithms for creating key pairs to be used in dual key encryption work. I have ...
2
votes
2answers
2k views

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents.

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents. How would you write a formal proof for this.