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

1
vote
2answers
32 views

Modular Arithmetic and prime numbers

With respect to the maths behind the Diffie Hellman Key exchange algorithm. Why does: (ga mod p)b mod p = gab mod p It might be fairly obvious, but what basic maths guarantees this? Why does the ...
5
votes
1answer
34 views

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime.

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime. Though I didn't check the statement with so many integers, but it looks like the equation never ...
6
votes
1answer
21 views

Smallest witness for checking the primality of a number

In this link https://primes.utm.edu/prove/prove2_3.html it is stated that the smallest witness for a composite number is always less than $2ln(n)^2$ , assuming the extended Riemann-hypothesis. ...
-3
votes
1answer
38 views

Find all natural numbers *a*, that satisfy the following: [on hold]

Find all natural numbers a for which $$ \frac{a^4+4}{17} $$ is prime.
7
votes
0answers
32 views

Does $S(n)$ contain infinite many primes?

Denote $p_j := j\text{th prime}$ and $S(n)\:=\sum_{j=1}^n p_j$ (The sum of the first $n$ primes). Is it known whether $S(n)$ is prime for infinite many $n$? OEIS gives the sum of the prime ...
0
votes
1answer
21 views

Euclid's Lemma using FToA

I would really appreciate some help understanding the following passage from my Real Analysis text. I have a professor who uses inquiry based learning, which basically means we all stare at each other ...
2
votes
4answers
50 views

If $S$ is the set of all numbers of the form $3k + 1$, prove that any number $a$ in the set is prime or product of primes.

$S = \{1, 4, 7, 10, \ldots \}$ $10$ and $25$ are prime with regard to the elements of $S$ but $16 = 4 \times 4$ and $28 = 7 \times 4$ are not. I have been stuck on this problem as I am not sure of ...
8
votes
1answer
59 views

Primes of the form $x^2+n\cdot y^2$, given $n$?

In an attempt to get to grips with algebra for a course I intend to follow, I was working through a bunch of exercise sheets. A series of questions got me wondering: Given an integer $n$, is there ...
2
votes
0answers
35 views

Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ? Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$ ...
-1
votes
1answer
40 views

How many ways can a quadratic form represent a prime?

Given $a,b,c,p\in\Bbb N$ with $b^2-4ac<0$ and $p$ is a prime with $\bigg(\frac{b^2-4ac}p\bigg)=1$, how many solutions $(x,y)\in\Bbb Z^2$ are there to $$ax^2+bxy+cy^2=p?$$
2
votes
0answers
49 views

“Race” of the primes modulo $1,3,7,9\ \pmod {10}$

The "race" starts with the prime $11$. The number of primes $1, 3, 7, 9 \pmod {10}$ is denoted after every occurring prime. Does the lead change infinitely often? And does every "runner" have ...
4
votes
1answer
63 views

$\tau$ and grouping of prime numbers

From Prime Number Theorem and this we can state $$\frac{p_n}{\bar{p}}\sim 2$$ or $$\lim_{n\to \infty} \frac{np_n}{(p_1 + \dots +p_n)} = 2$$ If we then look at the fluctuations in the graph of $$f(n) ...
2
votes
2answers
58 views

Prove that $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \pmod p$

I'm trying to prove the statement $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} \equiv 0 \mod p$ and I don't really know where to start. Obviously $\sum_{t=1}^{p-1} \frac{t^2-1}{t^2+1} = 2\sum_{t=1}^{(p-1)/2} ...
2
votes
2answers
47 views

Is every positive integer relatively prime to $1$?

Because $\gcd(k, 1) = 1$ where $k > 0$ is an integer.
5
votes
2answers
49 views

Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm.

Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm. Hint: why can't $p = 5$ or 7? So I have done the two hints and in both cases I get a 9 in my set of numbers, ...
6
votes
2answers
66 views

Does every prime of the form $4k+1$ divide a number of the form $4^n+1$?

While playing around with Fermat's little theorem I was asking myself the question in the title and I can't answer it...
0
votes
1answer
29 views

Can Stirling's approximation be used to obtain lower and upper bound for $\pi(x)$?

The Willan's formula is given as follows (taken from Ribenboim's Little book of bigger primes): $$ \pi(x)=\sum_{j=2}^{x}f(j) \text{ where } ...
0
votes
0answers
34 views

Trial division formula [on hold]

I'm not very good with mathematic notation, I'm trying to describe a formula for trial division. Can anyone point me in the right direction or provide an answer? Also please do explain the notation ...
5
votes
1answer
54 views

Proving that and how $ \frac{1}{n}\sum\limits_{p\le n}\lfloor n/p \rfloor - \sum\limits_{p\le n} 1/p $ approaches $0$

Let $p$ denote a generic prime number. By Mertens' second theorem, the sequence $$\sum\limits_{\ p \le n} \frac1p - \log\log n$$ converges to the Meissel-Mertens constant $M\approx 0.2614972$. Now let ...
5
votes
3answers
135 views

What's the smallest known interval containing at least one prime number?

Wikipedia says that Dusart proved in 2010 that there's at least one prime between $x$ and $\left(1 + \frac{1}{25\ln^2x}\right)x$ for $x \geq 396738$. For $x_0 = 396738$, this implies a prime between ...
3
votes
1answer
78 views

Which constellations of primes recur forever?

Having derived much joy and learning from the answers I have received to four previous questions, let me ask one more. Let a constellation of primes be a set of primes that stand in certain fixed ...
0
votes
0answers
15 views

Primes and even numbers [duplicate]

Can every even number be written up as the difference of two primes? And in either case could you prove it? $$ e.g.\space 8 = 31-23 \space and \space 10 = 41-31$$
1
vote
0answers
28 views

Ways Of Finding Primes and If they are efficient

I am currently in middle school and love number theory. I try and do a proof every day and today I was working on a relatively simple one involving primes. I proved that every prime above 5 can be ...
2
votes
1answer
74 views

Why is $p_n \sim n\ln(n)$?

I know that the prime number theorem states that the number of primes less than $x$ is approximately $\frac{x}{\ln(x)}$. However, why does this mean that $p_n \sim n\ln(n)$? (where $p_n$ is the $n$-th ...
0
votes
1answer
31 views

Lower bound for $\Pi(n)$ - viability of probabilistic theory

Can somebody check the validity of my arguments below, and tell me why its wrong or right? Consider the sequence of non-negative integers. Let $a_0=0, a_1=1, ..., a_i=i,...$ Divisiblilty of $a_i$ ...
0
votes
0answers
18 views

The distribution of prime and semi-prime.

Let $\alpha$ be an integer and $\rho_1,\rho_2$ some prime such that $\alpha=\rho_1\cdot\rho_2+1$, and $\beta$ the number of all semi-prime less than or equal to $\alpha$. Prove ...
0
votes
2answers
99 views

How many prime numbers we need? [on hold]

If we have some not prime number $n > 1$ we always can make prime factorization. For this operation we need $m$ prime numbers. Is there any way to prove that for given $n$ we can use no more then ...
2
votes
2answers
50 views

Is the sequence $\{0,2,6,12,20,30,…,n(n+1)\}$ admissible for every natural $n$?

Look here : https://en.wikipedia.org/wiki/Prime_k-tuple for the definition of an admissible sequence. I wonder if the sequence of differences of primes can be $\{0,2,4,6,8,...,2n\}$ for every ...
1
vote
1answer
25 views

Dirichlet theorem

Can anyone give a simple number theory proof for the Dirichlet theorem? Statement of Dirichlet theorem:given any two numbers a and b whose g.c.d is 1,Prove that infinitely many primes exist in the ...
-3
votes
0answers
17 views

what is formula to this eqution [(256)16]1/32+[(169)6]1/12 [on hold]

how to solve this equation [(256)16]1/32+[(169)6]1/12 what is formula of this? What is the closed form expression for this? What is the right domain for this Hamiltonian 2? what is the right ...
4
votes
1answer
55 views

Is every sufficiently large even integer the sum of distinct primes?

Is every sufficiently large even integer the sum of (any number of) distinct primes? No doubt this question has been asked before; does the conjecture/theorem have a name? It is related to ...
1
vote
1answer
56 views

Smallest twin-prime-pair exceeding $10^{1000}$

I found the twin-prime-pair $$\large 10^{1000}+9705092\pm 1$$ with PARI/GP. Is this the smallest twin-prime above $10^{1000}$ ? A general question to the search of twin primes : The prime number ...
2
votes
2answers
65 views

How do I find(isolate) the n-th prime number?

So I wanted to solve this SPOJ problem and I did some research about finding the n-th prime number. This formula came across and it stated that the n-th prime must be in this range: $n \ln n + ...
5
votes
0answers
46 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
1
vote
0answers
26 views

Is there a tighter approximation for the least prime gap of a given length?

This link https://primes.utm.edu/notes/gaps.html gives a definition of the maximal gaps. For a number $g$ , $p(g)$ is the smallest prime $p$ followed by at least $g$ composites. The estimate is ...
0
votes
0answers
23 views

Chebyshev's original proof of Bertrand's postulate

I'm looking for the original Chebyshev's proof of Bertrand's postulate. It would be great if someone could provide me the link to the article. Thank you in advance,
4
votes
4answers
73 views

Books on Prime numbers

I am a graduate student and have just finished Burton's book on number theory. Now I want to read further on prime numbers. Does anyone have any suggestion?
1
vote
1answer
35 views

For every natural integer $N>3$ there are at least two distinct prime numbers $p$ and $q$ such that $\dfrac{p+q}{2}=N$ and $N-p=q-N$, $(p<q)$.

I'm not sure but this problem may be similar or related to Goldbach conjecture? Any proof/disproof, insight and opinion is appreciated, thanks.
-1
votes
1answer
30 views

Is there a number which describes the approaching ratio of twin primes to other primes? Or a formula for the change in density of twin primes?

Could someone shed some light on what we know about the density of twin primes? I find that it seems to be empirically true that the density of prime gaps increases as $\log(x)$ does for any gap. ...
1
vote
1answer
18 views

Large pairwise coprime sets

Say that a set $S\subseteq\Bbb N$ is pairwise coprime if every two elements of $S$ are relatively prime. Denote by $f(n)$ the size of a maximal pairwise coprime subset of $\{1,...,n\}$. What is ...
3
votes
2answers
86 views

New deterministic primality test for numbers of the form $p\cdot 2^n + 1$

Edit: Sorry, there was an error. Old Claim (not true because there is a counter-example): Let $p$ be prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N = p\cdot 2^n+1$ is prime, if and only ...
3
votes
0answers
24 views

Kronecker symbol vs. Koblitz symbol

In Koblitz, Introduction to Elliptic Curves and Modular Forms on page 188 it is defined $$\left( \frac{-1}{j}\right)=0$$ in case $j$ is even. Apart from that definition $\left( \frac{c}{d}\right)$ is ...
0
votes
0answers
37 views

Why does $\frac{x^n}{n^x}$ stop growing at the approximate value of $\pi (n)$?

I noticed while playing around with these functions that $n^x$ will start slow and then speed up really fast in its growth rate. While $x^n$ grows more slowly, but faster than $n^x$ at the start. ...
1
vote
0answers
55 views

Does anyone recognize this graph?

It's a plot of the following: Let $$f_{(n)} = \frac{np_n}{(p_1 + \ldots + p_n)}$$ so that $$g_{(n)} = \left|\space f_{(n)} - f_{(n-k)}\right| $$ where $n > k$ and $k = 5$ in this example. For ...
0
votes
1answer
48 views

Show that there exists $s, t \in S$ such that $\gcd(s, t)$ is a prime

Let $S$ be a set containing finitely many positive integers greater than 1 with property: for all $n \in \mathbb{Z_+}$, there exist $s \in S$ such that $\gcd(s, n) = 1$ or $\gcd(s,n) = s$. Show that ...
1
vote
1answer
35 views

Why hash table size is prime? [closed]

In computer science, the size of the hash table is recommended to be prime. What is the property of prime number that makes it recommended to be the size of hashtable?
-3
votes
0answers
44 views

If $p$, $q$, and $r$ are all odd primes, which of $p^2-q^2+1$, $pqr+3$, and $(p+2)(r+2)+1$ can be prime? [closed]

If $p$, $q$, and $r$ are all odd primes, which of the following might also be a prime? a) $p^2-q^2+1$ b) $pqr+3$ c) $(p+2)(r+2)+1$
0
votes
2answers
63 views

Proof that every positive integer has at most one prime factor greater than it's square root?

I read the statement in the title somewhere but I can't find any proof. For a positive integer $n$, why can't there be 4 numbers $a, b, c, d$ ($b$ and $d$ are prime) for which $a < \sqrt{n} < ...
2
votes
0answers
36 views

Legendre symbol identity

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
-1
votes
1answer
59 views

Prove that $n^m+x$ is not prime generally if $n+x$ is (in $\Bbb N$)

If $n + x$ with $n, x \in \Bbb N$ is prime, is it possible to prove generally, that $n^m + x$ with $n, x, m \in \Bbb N$ is not prime for at least one $m$? If yes, how can this be done? EDIT: There ...