Prime numbers are natural numbers greater than 1 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

11
votes
1answer
254 views

Intuition behind Erdős proof of the infinitude of prime numbers

Suppose by contradiction that there are finitely many primes, namely $p_1, p_2,...,p_k$, where $k$ is a natural number. Now consider another natural number $n$, and all natural numbers $m \leq n$. ...
3
votes
3answers
121 views

If $p \mid m^p+n^p$ prove $p^2 \mid m^p+n^p$

Prove that for a prime $p>2$, if $p \mid m^p+n^p$, prove $p^2\mid m^p+n^p$ From Fermats theorem I concluded $p \mid m+n$, so $p^2\mid (m+n)^p$. How do I proceed next? Any hints are welcomed.
0
votes
2answers
49 views

Let $a, b, c, m, n$ be integers, $m, n$ not both $0$.

(a) Prove that if $am + bn = c$, then $hcf(m,n)|c$ (b) Prove that if $am + bn = 1$, then $hcf(m,(n) = 1$ (c) Prove that $m/hcf(m,n)$ and $n/hcf(m,n)$ are coprime. Question on recent review homework ...
1
vote
2answers
67 views

If $30$ divides $p_1^4 + p_2^4 + \ldots + p_{31}^4$. Prove that $p_1=2$, $p_2=3$ and $p_3=5$.

Let $p_1<p_2<\cdots<p_{31}$ be prime numbers such that $30$ divides $p_1^4 + p_2^4 + \cdots + p_{31}^4$. Prove that $p_1=2$, $p_2=3$ and $p_3=5$. No clue how to start..Hints are welcomed.
2
votes
1answer
112 views

Minimum Argument Difference to Make the Lower Bound > the Upper Bound

Assume $g$ is a function that grows asymptotically as $$ g(n) \in\frac n {log(n)} + O(\sqrt n),\,n \in \Bbb N\tag1 $$ I wish to find $h(n)$ such that $$ g(n) \le g(n+h(n)). $$ i.e. Given the bounds ...
1
vote
1answer
111 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
87 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
96 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
63 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
260 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
91 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
70 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
479 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
120 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
1k 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
89 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
234 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
125 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
45 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
407 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 ...
1
vote
2answers
67 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
124 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
24 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 ...
17
votes
0answers
299 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 ...
1
vote
2answers
61 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
82 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
47 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
71 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
112 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
92 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
247 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
65 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
75 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
240 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 ...