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
48 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 ...
12
votes
3answers
668 views

Finitely many Supreme Primes?

A challenge on codegolf.stackexchange is here: http://codegolf.stackexchange.com/questions/35441/find-the-largest-prime-whose-length-sum-and-product-is-prime The challenge is to find the highest ...
0
votes
1answer
62 views

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

How true is it that $$ \pi(x)\approx\sum_{n=1}^{\infty}\left[\dfrac{\mu(n)}{n}\left(\dfrac{1}{\log(x^{1/n})}\left(\sum_{j=1}^{\lfloor x^{1/n}\rfloor}\sum_{k=1}^{\lfloor ...
0
votes
1answer
63 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
41 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
140 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
37 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
36 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?
0
votes
0answers
24 views

A Question Related to Zsigmondy's Theorem

I am wondering if there is a way to prove the following statement, which bares some resemblance to Zsigmondy's Theorem. I am not sure if the statement is true, but it seems as though it should be. ...
3
votes
0answers
42 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) \\ ...
2
votes
0answers
32 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
87 views

Number theory proof regarding primes and the number of digits of the prime [duplicate]

How would you prove that if given a prime each of whose (decimal) digits is equal to $1$, then the number of its digits is a prime. (It is not known if there exists infinitely many such prime)
0
votes
1answer
141 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
66 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
71 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
42 views

Computing question: A quadratic which gives primes [on hold]

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
23 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
54 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
31 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
29 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
-2
votes
1answer
104 views

A Twin Primes Sequence [on hold]

How to prove the relation below and is it enough significant to prove the infinitude of the twin primes? For every twin primes $x,y$ there exists $\alpha,\beta$ positive integers such that ...
12
votes
0answers
184 views
+150

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$ ...
28
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 ...
4
votes
5answers
125 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
25 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
votes
0answers
64 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. ...
3
votes
1answer
52 views

If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So ...
-3
votes
1answer
83 views

A new Set of Primes [on hold]

Considering the following do there exists a fatal error? There exists infinitely many primes $\zeta$ and $\beta$ such that ...
-3
votes
1answer
50 views

Billion-Digit Prime Number [closed]

I am trying to identify a billion-digit prime number in the form 10^(10^9) + x. This number could be found in the form NextPrime[10^(10^9)], but I do not want to look at a billion digits. To do this, ...
3
votes
0answers
89 views

The n-envelope problem

This is original problem: You have n number of envelopes, and 100 $1 bills. you have to put these bills in the envelopes in such a way that any amount between 1 to 100 can be reached just by ...
4
votes
0answers
67 views

Are large prime numbers kept secret? [duplicate]

I've read several times that modern cryptography is based on the fact that multiplying two primes is easy, whereas getting the prime factorization of a random big integer is very hard. (see here) ...
1
vote
1answer
53 views

Limit of Sum $\sum \frac{p(k+1) - p(k)}{p(k)^2}$ ? (corrected)

This is a re-post with my (corrected) earlier typo in red as a reminder. The question is about $$(A)\hspace{10mm}\lim_{n \to \infty} \sum_{k=\color{red}2}^{n} \frac{p(k +1) - p(k)}{p(k)^2} = ...
3
votes
1answer
104 views

Showing that if $p$ is prime, then $(p^4 + 4)$ can't be prime

I want to show that if $p$ is prime, then $(p^4 + 4)$ can't be prime. I guess Fermat's little theorem may help, but I can't figure out how to use it for the proof. Can anyone point me in the right ...
2
votes
1answer
96 views

Are there infinitely many prime numbers? [duplicate]

I will post my own answer below. That should not deter others from answering. There are many ways to prove this.
1
vote
1answer
26 views

Sizes of Blocks of Consecutive Integers Divisible by at Least One Prime Less than or Equal to $r$.

Let $f(r)$ be the largest integer such that there exists a block of $f(r)$ consecutive integers each divisible by some prime that is less than or equal to $r$. For example, $f(2)=1$ because it is ...
3
votes
0answers
53 views

An Inequality with Prime Numbers

Let $m\geq 8$ be an integer, and let $q$ be the smallest prime that is greater than $m$. Let $p$ be a prime that satisfies $q\leq p<q^2$, and let $p_0$ be the smallest prime such that ...
2
votes
1answer
42 views

For an integer $n \geq 2$, let $m$ be the largest positive integer less than $n$ such that $m \mid n$. [closed]

Consider an integer $n \geq 2$, and $m$ the largest positive integer less than $n$ such that $m \mid n$. Then $n = mk$ for some positive integer $k$. Prove that $k$ is a prime number.
1
vote
2answers
216 views

Visualization of Eratosthenes’ sieve

In otherwise great paper on prime numbers, I found following visualization of Eratosthenes’ sieve: I found it somewhat scary and confusing. Is there any better visualization of Eratosthenes’ sieve ...
1
vote
0answers
43 views

Prime bounds under RH

Continuing from here, since $$ \sum_{k=1}^{\lfloor\log(n)\rfloor}\dfrac{\pi(n^{1/k})}{k}=\operatorname{li}(n)-\sum_{k=1}^{\infty}2\ ...
0
votes
1answer
38 views

Existence of at least one prime for all sequences in the family of sequences

Prove or disprove that for a fixed $n \in N$, there exists at least one prime among the integers of the form $2^{k}n+2^k-1$ for an arbitrary $k \in N$.
0
votes
2answers
126 views

$9n^2-4$ only generates one prime? Why?

Instead of doing the work I was supposed to be doing, I played around with some numbers, and I noticed that for $n\in\mathbb{N}$, $9n^2-4$ only seems to generate a prime for $n=1$. Can anyone ...
0
votes
4answers
111 views

Is at least one of $6k + 1$ or $6k-1$ prime?

We know that any prime number ( $> 2,3$) can be written in the form $6k+1$ or $6k-1$. Is it necessary that at least one of $6k+1$ or $6k-1$ is a prime number ?
0
votes
1answer
40 views

Q: Understanding Answer of 2012 AMC 8 - #18

The problem is: "What is the smallest positive integer that is neither prime nor square and that has no prime factor less than 50?". The solution for this problem goes like this: "Since the integer ...
0
votes
2answers
109 views

Congruence modulo primes or in a polynomial ring over ${\rm GF}(2)$

Let $p, q$ be primes. Then the linear congruence $$ap \equiv r\pmod q$$ can be solved for $a\in\mathbb Z$ and will have a unique solution for each value of $r$ such that $0\leqslant a<q$. Am I ...
1
vote
2answers
31 views

Prove that 1 is the only “common” divisor of the integers n and n+2

Let n be any odd integer. Prove that 1 is the only "common" divisor of the integers n and n+2. I think you have to find gcd(n, n+2) and say that since n odd then then n+2 will also be odd. Thus n + ...
0
votes
0answers
44 views

Fast check of safe primes or Sophie Germain primes

If $p=2q +1$ with $p,q$ prime then $p$ is called safe prime and $q$ is a Sophie Germain prime. I want a faster algorithm for a safe prime test than doing two primality checks for $p$ and $q$. In ...
7
votes
1answer
165 views

Prove $18080108080 \sum_{k=0}^{1560-1} 10^{10k}+1$ is prime

I saw this fact on twitter: I would like to know how one would show this number is prime. Is there an elementary way to show that this number is prime? Is there a simplified primality testing ...
2
votes
1answer
82 views

Prime number upper bound

I am reading some written notes about a proof I do not understand, maybe some informations are missing. The result that has to be proved is the following: if $p_n$ is the $n$-th prime number, ...
1
vote
0answers
83 views

How I could transform this into product over primes :$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+…\frac{1}{2^p-1}$?

1)Can I transforme this sum into product OVER primes:$s_p$= $\frac{1}{2^2-1}+\frac{1}{2^3-1}+....\frac{1}{2^p-1}$ ? Note : p is prime number and ${2^p-1}$ is prime 2)I would be interest to know ...
0
votes
1answer
27 views

Largest $k$ such that $(p-k) = \lceil \sqrt{(p-2k) p} \rceil$

Assume $p \in \mathbb P.$ Assume $0<p-2k<p$ and the next square larger than $p(p-2k)$ is $(p-k)^2$. It is trivial to show that $p(p-2k)+k^2$ is a square. Simply $p(p-2k)+k^2 = (p-k)^2.$ ...