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

0
votes
1answer
111 views

Is there a forumla for number of primes preceding a natural number?

I am guessing there is no known analytical function which gives such a formula. This question came to mind while attempting a rather basic proof. I am trying to show that the number of primitive ...
4
votes
4answers
163 views

Proof of equivalence?

How do I prove that if two numbers $a$ and $N$ are co-prime, then in the equation: $$ax ≡ ay \pmod N$$ necessarily $x ≡ y \pmod N$
4
votes
3answers
181 views

Prime number in a polynomial expression

Will be glad for a little hint: let x and n be positive integer such that $1+x+x^2+\dots+x^{n-1}$ is a prime number then show that n is prime
1
vote
3answers
310 views

Express the power of a natural number with the power of the product of prime factors

Given a natural number say $n \in \mathbb{N}$ with a prime factorization $p_1^{m_1} \cdot p_2^{m_2} \dots p_k^{m_k}$. If you take product of the prime factors $p_1 \cdot p_2 \dots p_k$ then the ...
1
vote
3answers
497 views

Are the first 1,000 prime numbers enough to build every Goldbach number up to 9 digits long?

I'm writing a basic computer program in which one of my requirements is to find the smallest pair of prime numbers that make up a Goldbach number (up to 9 digits long, non-inclusive). The user ...
4
votes
1answer
168 views

Primitives roots of $p$ and $p^2$.

It is well known that for any primitive root $g$ of a prime $p$, either $g$ or $g + p$ is a primitive root of $p^2$ Do there exist any primes for which $g$ is a primitive root of $p^2$ for all ...
1
vote
1answer
209 views

Numbering primes within a range.

$$n\ln n + n\ln\ln n−n < p_n < n\ln n+n\ln\ln n \mbox{ for } n\geq 6$$ This is the range where the $n$-th prime must lie. However sieving within this range generates a large number of primes. ...
8
votes
0answers
198 views

How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?

Is there an easy way to compute the following question: How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes? The only thing that ...
1
vote
1answer
270 views

How to select the values X and Y in the Sieve Of Atkin Algorithm

I came to know Sieve of Atkin is the fastest algorithm to calculate prime numbers till the given integer. I am able to understand the sieve of Eratosthenes from wikipedia page but i am not able to ...
1
vote
2answers
160 views

What are the specifics and the possible outputs of Pollard's Rho algorithm?

I'm trying to implement a simple prime factorization program (for Project Euler), and want to be able to use Pollard's Rho algorithm. I read the Wikipedia, wolfram|alpha, and planet math explanations ...
0
votes
1answer
434 views

Contiguous prime numbers with MPI (Want more ideas for an efficient algorithm)

I am a programmer. I am working with Message Passing Interface (MPI) in C. I do a program that consist on finding the contiguous prime from 1 to 10,000,000. I already do it! but I do it with trial ...
31
votes
4answers
1k views

Could G. H. Hardy make a product of two primes so big he couldn't find out which?

This question of course began as a slightly irreverent play on the riddle, "Can God make a stone so big He can't lift it?" Then I wondered about the answer. Is it possible to exhibit a number that is ...
0
votes
1answer
1k views

finding the greatest perfect square dividing an integer

how can we find the greatest integer which is a perfect square and which divides an integer? I believe factorisation can be used here but am not sure how to get the result out of it for all prime, ...
5
votes
1answer
2k views

Finding a point on Archimedean Spiral by its path length

I've been curious about Archimedean Spirals and their relations to Sacks Spirals and prime numbers. I would like to draw some visualizations of the points with a given distance from the center, ...
1
vote
1answer
125 views

Distribution of Subsets of Primes

Primes may be divided in to sets: $p=4n\pm1$. Gauss showed, that if $p=4n+1$, it may be written also as $p=a^2+b^2$. From LagrangesFour-SquareTheorem, we know that $g(2)=4$, where 4 may be reduced ...
1
vote
1answer
266 views

Sequence of first differences strictly increasing?

If $ \pi (x) $ := number of primes $ \leq x $, the operation $T(x_{n+1}) = x_{n+1} - \pi(x_{n+1}) = x_n$ gives a sequence whose elements are those for which repeated application of T gives the ...
3
votes
2answers
271 views

Statistical observations about primes

Are there statistical observations about prime numbers showing that primes are not random? For example obviously primes are $1$ or $-1$ mod $6$, but are these remainder distributed equally? What I ...
29
votes
3answers
33k views

Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly? Thanks
18
votes
1answer
451 views

Is the clustering of prime powers merely coincidental?

$2^3$ and $3^2$ are close together; $11^2$, $5^3$, and $2^7$ (121, 125, and 128) are close together; $3^5$, $2^8$, and maybe $17^2$ (243, 256, and 289) are close together. $7^3$ is close to $19^2$ ...
25
votes
1answer
854 views

How many primes does Euclid's proof account for?

This is a passing curiosity, and I haven't found any duplicates, so I thought I'd share my thoughts. In the most basic (or at least the most famous) proof of the infinitude of prime numbers, due to ...
1
vote
0answers
163 views

Infinitely many primes in every row of array?

Friend of mine gave me this problem : Consider the following array of natural numbers : $\begin{array}{ccccccccc} 1 & 2 & 4 & 7 & 11 & 16 & 22 & 29 & \ldots \\ 3 ...
1
vote
1answer
140 views

Conditional equivalence of expression to cardinality of primes on square intervals

This is an exercise to show that $$\frac{\pi((x+1)^2) - \pi(x^2)}{\pi(x- \pi (x)) } \sim 1 $$ assuming the unproven hypothesis: $\displaystyle \pi (x^2, x^2+x^{2( \theta)}) \sim \frac{x^{2( ...
1
vote
1answer
250 views

Something weaker than Goldbach's Conjecture

Inspired by this question on the "Sum of a odd prime and a odd semiprime as sum of two odd primes?", I wonder, if it is possible to show, that every even number $2n\ge 12$, can be written as a sum of ...
4
votes
2answers
127 views

Asymptotics of products of primes

Let $P(n)=\{p \leq n: p\text{ is prime} \}$. For given $N$ and $n$, what's a good approximation for $|S(N,n)|$, where $S(N,n)=\{x<N: \forall p\text{ prime, s.t. }p|x \to p \in P(n) \}$. In other ...
6
votes
0answers
145 views

Density of products of a certain set of primes

I have an infinite set S of prime numbers with relative density 0 (that is, $\lim_ns_n/p_n=\infty$ with $S=\{s_1,s_2,\ldots\}$ and $s_1 < s_2< \cdots$). I would like to find the size (in some ...
1
vote
1answer
108 views

A pattern in distribution of near-primes less than $2^n$

Let $\pi_k(2^n)$ be the number of almost-primes (numbers with k factors including repetitions) less than $2^n$. I noticed that for large values of n and values of k near n, a sequence $\{\pi_k\}$ ...
2
votes
1answer
294 views

Prime numbers in a formula

I am not able to give a proof of the following statement: given an integer number $k$, we consider the following expression: $$x=\sqrt{k^3}-\sqrt[3]{k^2}$$ Show that you can get infinite prime numbers ...
21
votes
2answers
938 views

Did H. Lebesgue claim “1 is prime” in 1899? Source?

John Derbyshire, in his text "Prime obsession: Bernhard Riemann and the greatest unsolved problem in mathematics" states that The last mathematician of any importance who did [consider the number ...
3
votes
1answer
269 views

Factor of the Euler Product at the Roots Of Zeta

The $\zeta$ function maybe written as Euler Product: $$ \zeta(s)=\prod_{p} \frac{1}{1-p^{-s}}=\prod_p e_p(s). $$ Now let's substitute $s$ with $\rho_k$, the $k$th root of $\zeta$, and have a look at ...
7
votes
5answers
579 views

Rational Roots of Riemann's $\zeta$ Function

A look at the first few zeros $$14.134725,21.022040,25.010858,30.424876,32.935062,37.586178,\dots$$ is in accord with Numerical evidence suggests that all values of $t$ (the imaginary part of a ...
0
votes
2answers
711 views

How to calculate all the prime factors of lcm of n numbers?

I have n numbers stored in an array a, say a[0],a[1],.....,a[n-1] where each a[i] <= 10^12 and n <100 . Now,I need to find all the prime factors of the LCM of these n numbers i.e., LCM of ...
2
votes
2answers
323 views

Application of prime number theorem

In the following I am referring to a small argument made in "A counterexample to Borsuk's conjecture" by Jeff Kahn, Gil Kalai (see http://arxiv.org/abs/math.MG/9307229) In this paper the authors bound ...
4
votes
2answers
133 views

Property of a sequence involving near-primes

Let $p_k(m)^2:=$ the square of $m^{th}$ number containing k prime factors, including repetitions. Empirically for smallish numbers and as a conjecture, it appears that for every m and sufficiently ...
1
vote
1answer
103 views

How to show $\pi (2n) \ge \log \binom{ 2n }{ n} / \log 2n$?

Proposition: $\pi (2n) \ge \dfrac{\log \binom{ 2n }{n} }{\log 2n}$ Since this is a follow up proposition to this one: How can we show that $\operatorname{ord}_{p}\left(\binom{2n}n\right) \le ...
31
votes
3answers
518 views

Do we really know the reliability of PrimeQ[n] (for $n>10^{16}$)?

The algorithm Mathematica uses for its PrimeQ function is described on MathWorld. That web page says PrimeQ uses, "the multiple ...
5
votes
0answers
98 views

Do we really know the reliability of Mathematica's PrimeQ[n] for (n>10^16)? [duplicate]

Possible Duplicate: Do we really know the reliability of PrimeQ[n] (for $n&gt;10^{16}$)? The algorithm Mathematica uses for its PrimeQ[n] function is described at ...
3
votes
1answer
317 views

Is $\frac1\pi \arctan \frac\pi{\ln x}- \frac1{\ln x}$ related to the trivial solutions $\zeta(-2n)$?

The Prime Counting Function $\pi(x)$ is given $$ \pi(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho}) - \frac1{\ln x} + \frac1\pi \arctan \frac\pi{\ln x} , $$ with $ ...
1
vote
0answers
182 views

Prime numbers, Hardy conjecture and Ulam spiral

I would like to know why if the Hardy Littlewood conjecture is true, this could explain the position of the prime numbers on the diagonal of Ulam spiral. Thanks.
10
votes
2answers
827 views

On proof of AKS primality test algorithm

Just studying the paper PRIMES is in P, although I've tried great efforts, some proofs are still not so clear(or obvious) to me, especially the proof of ...
1
vote
2answers
1k views

How to prove $ \phi(n) = n/2$ iff $n = 2^k$? [duplicate]

How can I prove this statement ? $ \phi(n) = n/2$ iff $n = 2^k $ I'm thinking n can be decomposed into its prime factors, then I can use multiplicative property of the euler phi function to get the ...
8
votes
2answers
1k views

How to prove $\phi(mn) > \phi(m)\phi(n)$ if $(m,n) \ne 1$

I need to prove that $$\phi(mn) > \phi(m)\phi(n)$$ if $m$ and $n$ have a common factor greater than 1. I have read up on the case where $m$ and $n$ are relatively prime, then ...
2
votes
1answer
226 views

Finding all prime numbers $x$ for which $24x+1$ is a perfect square

Clearly, a prime fits the criteria if the result of $\sqrt{24x+1}$ is an integer. By trial and error, I have found that seemingly the only primes to fit this criteria are 2, 5 and 7. How would I go ...
5
votes
5answers
801 views

Is it possible to get 1/3 without dividing by 3?

So I need to divide a rectangle into 3 equals parts, but without fractions. It's one of those old "You have two jars of two sizes and need to get an exact amount of some other size" type problems, ...
11
votes
1answer
384 views

What is the intuitive meaning of “conspiracy” in number theory?

Assuming very little number-theoretic background from my part, could you please explain me what is the intuitive meaning behind "conspiracy" in number theory? There is no formal entry on Wikipedia and ...
1
vote
2answers
2k views

How to work RSA encryption/decryption

I need an array populated with characters and integer keys for each, and I want to, using this set, encode messages, and then decode them later on . Essentially I am trying to write RSA algorithm for ...
2
votes
1answer
1k views

Trying to calculate RSA decryption key

I am testing a piece to encrypt and decrypt messages, and I am not 100% on why the algorithm does not seem to work as expected. My test encryption key $e =27$. My primes $p = 263$ and $q = 911$. And ...
6
votes
1answer
580 views

Summing over General Functions of Primes and an Application to Prime $\zeta$ Function

Along the lines of thought given here, is it in general possible to substitute a summation over a function $f$ of primes like the following: $$ \sum_{p\le x}f(p)=\int_2^x f(t) d(\pi(t))\tag{1} $$ and ...
4
votes
3answers
741 views

For every $n \ge 1$ there exist uniquely determined integers $a \gt 0$ and $b \gt 0$ such that $n = a^2b$ where $b$ is square-free. [duplicate]

Possible Duplicate: Show that every $n$ can be written uniquely in the form $n = ab$, with $a$ square-free and $b$ a perfect square I am trying to prove that for every $n \ge 1$ there ...
5
votes
4answers
2k views

How can we prove that among positive integers any number can have only one prime factorization?

I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
0
votes
2answers
651 views

Fermat's Little Theorem - Reducing Exponents

Just search for the string Reducing Exponents on this page. In the example it says $7^{147} = ((7^{10})^{14}) \cdot (7^7)$ And since $(7^{10}) \mod 11 = 1$, $((7^{10})^{14})\cdot(7^7) \mod 11 = (7^7) ...