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

2
votes
1answer
211 views

Unusual behavior of 210 and 199 regarding prime numbers

Adding 210 to 199 over and over again, you get 8 more primes that can be arranged together into a 3x3 magic square: 1669 199 1249 619 1039 1459 829 1879 409 Is there any other pairs of numbers ...
3
votes
1answer
95 views

Golden Ratio of Primes (Amateur)

Unable to find information elsewhere, so I'll try here. What two consecutive primes are closest to producing the Golden Ratio? Or two of any Primes? Has this been determined? Thanks!
0
votes
1answer
95 views

Computing infinite product over primes

How can I compute $$ \prod_p \left(1+\frac{k}{p}\right)\exp(-k/p) $$ where $0<k<e$ and the product is over all primes $p$? Background L. G. Sathe proved [1] that there are $$ ...
0
votes
2answers
53 views

Dividing a product of different primes by another prime

A relatively straight forward question. If I were to multiple any amount of different prime numbers together say 7*3*11, is it possible to divide the product by a single other prime number say 23 and ...
2
votes
3answers
59 views

Smallest prime factor of a Mersenne number

The Mersenne numbers $M_n$ are integers of the form $2^n-1$, where $n$ is a positive integer. In the case when $n$ is a prime, are there any results known on the smallest prime factor, $p_n$, of ...
1
vote
1answer
34 views

Given a sequence, construct a function whose integral is equal to the sum of the sequence

Let $P_n$ be the sequence of prime numbers, where $P_0=2$. Given $m\in\mathbb{N}$, how can we construct $f(x)$ such that: $\displaystyle\forall{0}\leq{i}\leq{m}:f(i)=P_i$ ...
2
votes
1answer
42 views

A slightly various form of Dirichlet's theorem on arithmetic progressions

Are there infinitely many primes of the form $2n(n+1)+1$?
3
votes
0answers
38 views

Are there infinitely many prime numbers in $a_n=\frac{7\times 10^n-1}{3}$?

In the array $a_n=\frac{7\times 10^n-1}{3}$, are there infinitely many primes? (when $n={7+16k},a_n$ is divisible by $17$, so there are infinitely numbers not prime)
1
vote
1answer
45 views

A different way to solve Chinese remainder theorem

I'm doing my homework about Chinese remainder theorem $x = a_1(\mod n_1)$ $x = a_2(\mod n_2)$ As I know, x can be found by using: $$x=\{\sum_{i=1}^na_iN_i(N_i^{-1}(\mod n_i)) \}(\mod N)$$ with ...
1
vote
4answers
155 views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
3
votes
1answer
89 views

Possible Prime Sum Pattern (Amateur)

Disclaimer: I’m an amateur, and have no advanced knowledge of math, so please forgive my ignorance as I’m just curious to know if I’ve stumbled upon something or not. Prime Numbers: 2, 3, 5, 7, 11, ...
6
votes
1answer
160 views

Does $\sum\limits_{n=1}^{\infty}\frac{1}{P_n\ln(P_n)}$ converge to the golden ratio?

The sum $\displaystyle\sum\limits_{n=2}^{\infty}\frac{1}{n\ln(n)}$ does not converge. But the sum $\displaystyle\sum\limits_{n=1}^{\infty}\frac{1}{P_n\ln(P_n)}$ where $P_n$ denotes the $n$th prime ...
3
votes
0answers
88 views

conjecture about prime numbers and distance between them

is there a name for this conjecture? Conjecture: given $p_n$ a prime number sequence where $p_1=2,p_2=3,\cdots$, then for all $n\in\mathbb{N}^*$ and $k\in\mathbb{N}$, holds that $\displaystyle ...
2
votes
2answers
35 views

Proof that if $k$ is the highest factor of any positive integer $n$ such that $k<n$, then $n/k$ is prime

It's straightforward to say that when $n$ is prime, $k=1$ since $k$ must be less than $n$. For the case where $n$ is not prime, I thought proving that the lowest factor of $n$ is prime would be the ...
4
votes
1answer
117 views

Elementary proof there are infinitely many primes of the form $4n+1$

My attempt: $4n+1$ is odd. Thus its decomposition must not contain $2$. Every odd number is either of the form $4k-1$ or $4m+1$. $(4m+1)(4k-1)$ is never of the form $4n+1$. So $4n+1$ has factors ...
-1
votes
2answers
107 views

Why is $y^{x-1}-1$ divisible by $x$?

I wanted to know if there is a way to prove that $y^{x-1}-1$ is divisible by $x$. Where $x$ is a prime number and is not equal to $y$, and $y$ is any positive whole number besides $1$. For example, ...
1
vote
0answers
46 views

Sequence of primes by concatenating digits in a given base.

Given a base, $b$ is there is a sequence $\lbrace a_n\rbrace_{n\geq 0}$ where $a_k \in \lbrace 1,2\cdots, b-1\rbrace$so that the sequence: $$b_n:= \sum_{k=0}^n a_kb^k$$ is a sequence of primes ...
1
vote
1answer
41 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
0
votes
4answers
132 views

How do you go about finding a 12 digit prime number?

How do you go about finding a 12 digit prime number?
3
votes
1answer
98 views

Meaning of Rays in Polar Plot of Prime Numbers

I recently began experimenting with gnuplot and I quickly made an interesting discovery. I plotted all of the prime numbers beneath 1 million in polar coordinates such that for every prime $p$, ...
3
votes
1answer
100 views

Why is $p_n\sim\sum_{k=1}^{n}\log(p_k)$?

Why is $$ p_n\sim\sum_{k=1}^{n}\log(p_k) $$ where $p_n$ is the $n$th prime? In addition, is it true that $$ n\log\left(\dfrac{\sum_{k=1}^{n}\log(k)}{\log(\log(n))}\right) $$ is a better ...
1
vote
0answers
46 views

Fast algorithm for generating consecutive primes larger than N

I'm looking for a fast algorithm to generate primes larger than a random 4096 bit number $N$. I know about the Sieve of Atkin, but AFAIK it can only be used to find all primes up to a certain limit. ...
3
votes
0answers
62 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 4

Following a previous question (here you'll find an introduction): A paper by Maier which refutes Cramer's Model suggests we should replace the heuristic "$\Bbb P(n\in\mathcal P)=1/\log n$" with ...
1
vote
0answers
26 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 3

Following a previous question (here you'll find an introduction): The book states that almost surely $$\pi_S(x+y)-\pi_S(x)=\mathrm{li}(x+y)-\mathrm{li}(x)+O(\sqrt y)$$ as soon as $y/(\log ...
2
votes
0answers
40 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 2

Following a previous question (here you'll find an introduction): The book states that using the convergence of the binomial distribution towards the Poisson distribution, it's easy to show that ...
2
votes
1answer
69 views

Finding an $n$ such that $n^2 \equiv -1 \mod p$

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists? Is there anything better than the brute-force approach up to $p-1 ...
14
votes
3answers
896 views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is to find the highest "supreme" prime: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime A ...
4
votes
1answer
147 views

Squeezing $\pi(x)$ out of $\psi(x)$

Can $\pi(x)$ be written in terms of $\psi(x)$? I can only seem to approximate it: $$ ...
0
votes
1answer
64 views

Probability with Primes

What is the probability that a positive divisor of $8748$ million is the product of exactly $20$ non-distinct primes? To try and solve this question I split up $8748$ into $2^8 \cdot 5^6 \cdot 3^7 $ ...
1
vote
2answers
44 views

Can't understand source of constant for prime counting function:

Consider the prime counting function $$ \pi(x) = \ the \ number \ of \ primes \ less \ than \ or \ equal \ to \ x$$ It is well known due to the sieve eratosthenes that given an integer $n$ and the ...
1
vote
4answers
159 views

Why didn't Fermat provide proofs of his theorems?

Apparently Fermat stated but didn't provide proofs of various theorems named after him, including Fermat's little theorem, Fermat's theorem on sums of two squares, Fertmat's polygonal number theorem, ...
1
vote
3answers
55 views

First index of number in that arithmetic progression which is a multiple of the given prime number

I have a prime number $p$, an arithmetic progression starting at $a$ with common difference $d$. How to find the first index of a term in that arithmetic progression which is a multiple of the given ...
0
votes
1answer
37 views

Probability and Prime Numbers

What is the probability that a positive divisor of 8748 million is the product of exactly 20 non-distinct primes?
1
vote
0answers
37 views

A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bears some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
4
votes
0answers
58 views

Euler's proof of divergence of sum of reciprocals of primes

On Wikipedia at link currently is: \begin{align} \ln \left( \sum_{n=1}^\infty \frac{1}{n}\right) & {} = \ln\left( \prod_p \frac{1}{1-p^{-1}}\right) = -\sum_p \ln \left( 1-\frac{1}{p}\right) \\ ...
3
votes
0answers
48 views

Are there any primes that are never a factor of a Carmichael number?

Is there a prime number $p$ that $p > 2$, and in which $p$ is a never a factor of any Carmichael number $C_n$: (p ∤ $C_n$) Extended this to all numbers $m$, instead of just $p$, will prove the ...
0
votes
1answer
125 views

Primes and the number of digits of the prime [duplicate]

Say $n$ has $k$ decimal digits, all of which are ones. How would you show that if $n$ is prime, then $k$ is prime?
0
votes
1answer
154 views

Let $x = 2441921$. Factor $x$ into a product of primes.

Let $x = 2441921$. Factor $x$ into a product of primes. I found that: $1519^2 −x=−134560= −2^5 ·5 · 29^2$ and $1541^2 −x=−67240= −2^3 · 5 · 41^2$. I am trying to figure out what to do from here. ...
0
votes
2answers
71 views

Represent a prime number $p$ congruent to $1$ $\pmod{3}$ by a sum of a square and $3$ times a square

I want to have a proof of the fact that each prime number is the sum of a square and three times a square (Euler). Context I read the answer to my former question about the number of points on an ...
1
vote
4answers
74 views

$p$ prime, $p\mid a^k \Rightarrow p^k\mid a^k$

Suppose $p$ is a prime and $a$ and $k$ are positive integers. Prove that if $pa^k$ then $p^k\mid a^k$. I have already proven that if $a,b,n\in\mathbb{N}$ and if $a^n\mid b^n$, then $a\mid b$. I tried ...
4
votes
0answers
47 views

Computing question: A quadratic which gives primes [closed]

This is about Project Euler Problem 27. The question is: Considering quadratics of the form $n^2 + an + b$, where $\lvert a \rvert < 1000$ and $\lvert b \rvert < 1000$ Find the product ...
1
vote
1answer
28 views

Length of smallest repunits divisible by primes

I want to prove this statement from Wikipedia: It was found very early on that for any prime p greater than 5, the period of the decimal expansion of 1/p is equal to the length of the smallest ...
3
votes
2answers
58 views

Prove that every non-prime natural number $ > 1$ can be written in the form of $n+(n+2)+(n+4)+…+(n+2m) = p$

I'm trying to prove that every non-prime natural number greater than $1$ can is equal to a sum of consecutive even or odd numbers. This can be resumed in : « $p,m,n \in ℕ$» , «$p > 1$» , «$n > ...
3
votes
0answers
36 views

Probability and sums of prime factors

Of the first N natural numbers, we select two different numbers at random. We'll call the greater one A and the lesser one B. What is the probability (P) that the sum of A's prime factors is LESS than ...
0
votes
0answers
30 views

Find a criterion for the primes p such that (5/p) = 1. [duplicate]

Find a criterion for the primes p such that (5/p) = 1. I don't understand this question it is like Determine all primes P such that (5/p)=1 I appreciate any help
29
votes
5answers
801 views

Can a Mersenne number ever be a Carmichael number?

Can a Mersenne number ever be a Carmichael number? More specifically, can a composite number $m$ of the form $2^n-1$ ever pass the test: $a^{m-1} \equiv 1 \mod m$ for all intergers $a >1$ ...
29
votes
2answers
4k views

Are weird numbers more rare than prime numbers?

By taking a look at the first few weird numbers: $$(70, 836, 4030, 5830, 7192, 7912, 9272, 10430)$$ It is certain that prime numbers occurs more often within this range of numbers. But are weird ...
5
votes
5answers
143 views

What is the proof to the fact that all prime numbers are 1 above or below a 6 multiple? [duplicate]

I was just having an argument with my friend and I dunno how we got here. But he suddenly said all primes are 1 above or below a multiple of 6. At first I tried a lot of primes but couldn't disprove ...
0
votes
1answer
27 views

Divisibility of $a^p-r$ and $a^q-r$ by the primes $p,q$

Let $p, q$ be prime and $a$ some positive integer such that $a = pq + r$ where $r$ is the remainder. Show that $p \mid a^p – r$ and $q \mid a^q – r$. Example: $p = 3$ and $q = 5$, $a = 17$ and $r = ...
1
vote
1answer
128 views

Andrica's conjecture implies Bertrand's Postulate?

Let $p_n$ denote the $n$th prime. Recall Andrica's conjecture, which states that $$\sqrt{p_{n+1}}-\sqrt{p_n}<1\quad\text{ for all }\,n.$$ I think Andrica's conjecture implies Bertrand's postulate. ...