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
1answer
110 views

Prove $p$$_n$$_+$$_1$ $<$ $2p_n$ without using the Bertrand's Postulate [closed]

Recently I have been researching on the Bertrand's Postulate to find and elementary proof of it. I have been able to prove that (if I have not made a very pathetic mistake) for any composite $n$ ...
4
votes
1answer
85 views

Motivation for using $L(1,\chi)$ in the proof of Dirichlet's Theorem

Having read the proof of Dirichlet's Theorem on the infinitude of primes in arithmetic progressions, I am left wondering what his motivation for studying $L(1,\chi)$ was and why it is reasonable that ...
1
vote
1answer
50 views

Finding solution of this equation in set of positive integers.

Could you help me to obtain solutions of the equation $2^{2k+1}-n^2 =1$ in set of positive integers, where $k$ and $n$ are positive integers. In case there is no solution, how to prove it. Thanks in ...
2
votes
1answer
93 views

About Fermat's last Theorem?beal etc

I could not get the point why people are so crazy about FLT?, I have seen that there is no much difference in Beal conjecture as well as FLT. Why people will pose such conjecture and announce prize ...
2
votes
2answers
113 views

Two positive integer with prime number

Let $a, b$ be distinct positive integers. Prove that there exists a prime $p$ such that when dividing both $a$ and $b$ by $p$, the remainder of $a$ is less than the remainder of $b$. How can i solve ...
2
votes
3answers
59 views

Prove that if m is prime and m|kl then either m|k or m|l.

Proofs homework question, here's what I've figured out thus far. Suppose m doesn't divide k. We need to then prove that m|l. If m doesn't divide k and m is a prime then we know m and k are co-prime ...
0
votes
3answers
247 views

Which is currently the best result on bounded gaps between primes?

In his paper "Bounded gaps between primes", Yitang Zhang proves that there are infinitely many pairs of prime numbers which differ by less than $70,000,000$. Which is currently the best improvement on ...
0
votes
2answers
89 views

sum of primes: approximate closed form?

Can you find this sum? $$\sum_{\text{primes } p \le n}p.$$ I don't know how to start, let alone do this sum! Thanks for your help. Kind regards.
3
votes
4answers
68 views

choose two prime numbers of length $k$

Maybe the following is a stupid question, if it is I apologize, and I encourage you to close my post. Suppose that I want to encrypt a message with the RSA cryptosystem; the starting rule is the ...
5
votes
2answers
346 views

Formula for prime counting function

I saw this formula on this paper page 2 $$\pi (n)=\sum_{j=2}^{n}\frac{\sin^{2}\left(\pi \frac{(j-1)!^{2}}{j}\right)}{\sin^{2}(\frac{\pi }{j})}$$ Where $\pi(n)$ is the prime counting function. Is ...
2
votes
2answers
116 views

A question on Zhang's result on prime gaps

I'd like to know which is the right way to mention the result that Yitang Zhang obtained in his paper "Bounded gaps between primes". In some places it is said that Zhang proved that there are ...
26
votes
1answer
991 views

What number appears most often in an $n \times n$ multiplication table?

The question is precisely as stated in the title: What number appears most often in an $n \times n$ multiplication table? Note: By "an $n \times n$ multiplication table" I mean the multiset ...
2
votes
1answer
109 views

finding square $k$ such that $k\mid 2^{k-1} -1$

Can we find a positive square integer $k>1$, which satisfies $k\mid 2^{k-1} -1$ ? If yes, what are such $k>1$ values? Here $k = n^2$ and $n$ is some positive integer. If we cannot find such ...
2
votes
0answers
58 views

Prime numbers series

Given the series of $g_n$ functions which have the multiples of $n$ as roots : $$g_n(x) = \sin \left( {\pi \over n} x \right) ; n \in \mathbb N^* $$ And the series of $f_n$ functions which have the ...
1
vote
1answer
72 views

Soft Question: What Does “Zero Density” mean in prime numbers?

I'm reading through an article on Paul Erdos (http://www.ams.org/notices/199801/vertesi.pdf) and on page 22 they mention the following: Calling 714 and 715 a “Ruth-Aaron pair”, we conjectured ...
0
votes
1answer
232 views

How come if $\ i\ $ not of the following form, then $12i + 5$ must be prime?

I know if $\ i\ $ of the following form $\ 3x^2 + (6y-3)x - y\ $ or $\ 3x^2 + (6y-3)x + y - 1, \ \ x,y \in \mathbb{Z}^{+},i \in \mathbb Z_{\ge 0}$, then $\ 12i + 5\ $ must be composite number, ...
1
vote
0answers
124 views

How come if $\ i\ $ not of the following form, then $12i + 5$ must be prime? [duplicate]

I know if $\ i\ $ of the following form $\ 3x^2 + (6y-3)x - y\ $ or $\ 3x^2 + (6y-3)x + y - 1, \ \ x,y \in \mathbb{Z}^{+},i \in \mathbb Z_{\ge 0}$, then $\ 12i + 5\ $ must be composite number, ...
1
vote
1answer
51 views

Probability distribution of count of factors for all numbers

Is the following known? Define "factor count" as the number of prime factors of the number, minus 1. For example: Prime numbers have a factor count of 1-1 = 0 4 has a factor count of (2 and 2)-1 = ...
0
votes
1answer
44 views

Can diagonalization mod p be generalized to diagonalization mod n?

When you diagonalize a matrix $A$, your $D$ matrix will be the similar to if you diagonalized $A$ mod $p$ (but $D$ will also be mod $p$ in this scenario). I'm having a brainfart moment here. Does $p$ ...
0
votes
1answer
30 views

Find one sum in the function of another sum only

Let $S = s_1 + s_2 + ... + s_n$, with $s_i \in N$. Let $M =(p_1*s_1 + p_2*s_2 + ... + p_n*s_n) \bmod{p_{n+1}}$, where $p_i$ indicates $i$-th prime. Find $M$ in the function of $S$ only. Source: ...
8
votes
1answer
390 views

Is every integer a quadratic residue mod some p?

Is every integer (say $d$) a quadratic residue mod some prime number $p$?
0
votes
2answers
134 views

Prove $x$ and $y$ in $y = x^2 + 2$ are prime only for $x = 3$ and $y = 11$?

Let $x$ be a positive integer and $y = x^2 + 2$. Can $x$ and $y$ be both prime? The answer is yes, since for $x = 3$ we get $y = 11$, and both numbers are prime. Prove that this is the only value of x ...
2
votes
2answers
71 views

Finding primes $p$ such that $ \dfrac {p+1}2$ and $\dfrac{p-1}4$ are primes [closed]

How many odd primes $p$ are there such that both $ \dfrac {p+1}2$ and $\dfrac{p-1}4$ are primes ?
1
vote
0answers
102 views

How to prove this sieve of prime form 12 * i + 5 is correct?

Step 1, make x columns rows data A and data B: ...
2
votes
0answers
43 views

Infinitely many primes in second-order recurrence

I just wondered about the following question: Suppose that we are given a homogeneous second-order recurrence relation, $x_{n+2}+ax_{n+1}+bx_n=0$ for all $n\in\mathbb{N}$. Can we choose integers ...
0
votes
2answers
65 views

Convergence of $\sum_{n=1}^{\infty}(\frac{H_n}{p_n}-\frac{n}{n^n})$

Does this diverge or converge ?? $$\sum_{n=1}^{\infty}(\frac{H_n}{p_n}-\frac{n}{n^n})$$ where $H_n$ is the nth harmonic number, $p_n$ is the nth prime. My impression is that it diverges, but I don't ...
0
votes
0answers
21 views

Primes, Pseudo primes and poulet numbers [duplicate]

Prove the following statement! If $a^2 -1$ is nor divisible by prime $p$, then $M$ is Fermat pseudo prime, where $M = AB$ and $A = (a^p -1)/(a-1)$ and $B = (a^p + 1)/(a+1)$
1
vote
1answer
119 views

Diffie–Hellman key exchange

Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula: G(generator), P(prime), A(side A), B(side B) A = G^A MOD P B = G^B MOD P AS is a secret ...
1
vote
1answer
41 views

Random conjecture

For any numbers $a$ and $b$ so that $a>b$ and $\text{gcd}(a, b)=1$, there exists a $c\in\mathbb{N^+}$ so that $a+bc$ is prime. I've only just tested this out with a few numbers, but I'm curious as ...
0
votes
1answer
22 views

Size of the “fixed” terms in the prime k-tuple conjecture

The prime $k$-tuple conjecture predicts that for $(a_{1}n + b_{1}), \ldots, (a_{k}n + b_{k})$ an "admissible" k-tuple, where the $a_{i}, b_{i}$'s are fixed, then there are $$ \sim c ...
15
votes
0answers
254 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
0
votes
2answers
59 views

Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
4
votes
1answer
81 views

Solutions to $3\cdot 5 p_1 \pm 37^n p_2 =2^b\cdot 29^m p_3$

Let $p_k$ be either primes larger than $40$ or equal to $1$. $n,m$ are larger than $0$ and $b$ is either $1$ or $2$. I'm searching solutions for the following equation: $$ 3\cdot 5 p_1 \pm 37^n p_2 ...
1
vote
0answers
46 views

Existence of a prime in an interval that is not a linear combination of two specified primes?

If $ n = \left( \frac{p+q}{2 } \right) + p q :p,q \in\mathbb{P}-\left\{2\right\} $ Can we show there exists a prime number $\theta : \sqrt{2n} \leq \theta \leq n $ and $\theta$ is not a linear ...
1
vote
1answer
29 views

How to formally write $f\left(k\right)={1\over p_1}+{1\over p_1p_2}+{1\over p_1^2p_2p_3}+{1\over p_1^4p_2^2p_3p_4}+\dots$

How do I write the following finite series as a sum of products: $$f\left( k \right) = {1 \over p_1} + {1 \over p_1p_2} + {1 \over p_1^2p_2p_3} + {1 \over p_1^4p_2^2p_3p_4} + \dots + {1 \over ...
0
votes
1answer
32 views

How to formally write $f\left(k\right)={1\over p_1}\left(1+{1\over p_2}\left(1+{1\over p_3}\left(1+\dots\right)\right)\right)$

How do I write the following finite series as a sum or product: $$f\left(k\right) = {1 \over p_1} \left(1 + {1 \over p_2} \left(1 + {1 \over p_3}\left(1+\dots \right) \right) \right)$$ …all the way ...
1
vote
1answer
66 views

Asymptotic behavior of $\pi (x)-\frac{x}{\log x}$

What is the asymptotic behavior of the function given below. $$f(x)=\pi (x)-\frac{x}{\log x}$$ $$f(x)=O(g(x))$$ What can be $g(x)$? Also what is the asymptotic behavior of the $h(x)=f(x)-g(x)$. My ...
1
vote
2answers
108 views

Dice-Game with two-twenty sided dice.

EDIT: I'll give this another try, trying to be clearer. The game is played like this: Player A roles two-twenty-sided dice and multiplies the two integers together to get some integer, say x, with $ ...
4
votes
2answers
88 views

Squares modulo 2^n

How many squares are there modulo $2^n$? If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.
2
votes
1answer
219 views

Error term of the prime number theorem in arithmetic progressions

It is known that if $(a, q)$ and $q\le (\ln x)^N$, then the following is true $$\sum_{k\le x, k\equiv a\pmod{q}}\Lambda(k) = \frac{x}{\phi(q)} + O(x\exp(-C\sqrt{\ln x}))$$ where $C$ depends only on ...
1
vote
1answer
41 views

show that there is some element x∈X whose stabilizer Gx is all of G where G is a group of order p^k, where p is prime and k is a positive integer

I'm having trouble with this problem: Suppose that G is a group of order p^k, where p is prime and k is a positive integer.
0
votes
1answer
63 views

Find the natural numbers so that n=2*a^2 ,n=3*b^3 ,n=5*c^5.Number theory problem.

Well here it is i spend almost 3 hours on this one!! Find the general form of the natural numbers that are twice a square ,tripple of a cube and 5 times a 5-ith power.Who is the smaller of them?.What ...
9
votes
9answers
1k views

A Poster About Prime Numbers [closed]

We're going to design a poster about prime numbers, which will appear in a mathematics magazine for middle school students. The poster should be both visually attractive and mathematically rich. Do ...
1
vote
2answers
73 views

Group Theory - Prime Index

The index $(G : H)$ of a subgroup H of G is the number of cosets of H. Let H be a normal subgroup with (G : H) = p, where p is a prime, and let a be an element of G that is not in H. Show that for ...
2
votes
2answers
211 views

Let q be an odd integer such that p = 4q+1 is prime.

Let $q$ be an odd integer such that $p = 4q+1$ is prime. a. Show that $(2|p) = -1$ b. Prove that $p | (4^q+1)$ So far I see that: $(2|p) = (-1)^{ (\frac{(p^2-1)}{(8)} )}$. Not sure if this helps ...
0
votes
2answers
179 views

Let p be an odd prime, q the smallest quadratic non residue (mod p). Prove q is prime.

So I have this problem; Let p be an odd prime and let q be the smallest positive integer which is a quadratic non residue (mod p). Prove q is a prime. So what I know is that, since q is the ...
2
votes
1answer
210 views

Prove the center of $G$ cannot have order $p^{n-1}$

Let $p$ be a prime, let $n>2$ be an integer, and let $G$ be a nonabelian group of order $p^n$. Prove the center of G cannot have order $p^{n-1}$. Honestly I have no idea where to start. Perhaps ...
1
vote
0answers
46 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
6
votes
1answer
167 views

Congruences and prime powers

I have just a small question that probably is not hard to answer, but I could not find and elegant solution to this question. Let $p$ and $q$ be prime numbers. $$5^q\equiv 2^q \pmod p$$ $$5^p\equiv ...
0
votes
0answers
41 views

If $k\le n$ and $k$ is relatively prime to $n$, there exists a prime $p$ such that $p \equiv k \mod n$.

I need to use this result in a step of a proof, but I am for some reason unable to justify it. It seems to be true, after trying some examples, but I am not sure why. If $1 \le k\le n$ and $k$ is ...