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

0
votes
1answer
50 views

question about the forms of prime numbers

I was thinking about primes earlier and I thought of a hypothesis that I have been unable to prove. I was wondering whether it was a known theorem and whether anyone knows a proof or can prove (or ...
5
votes
2answers
568 views

Is every non-square integer a primitive root modulo some odd prime?

This question often comes in my mind when doing exercices in elementary number theory: Is every non-square integer a primitive root modulo some odd prime? This would make many exercices much ...
1
vote
2answers
139 views

Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
2
votes
2answers
130 views

Formula for the number of solutions of the congruence equation $xy-wz=0$ over $\mathbb{Z}_p$?

The equation $xy-wz=0$ has 10 solutions over $\mathbb{Z}_2$ and 33 solutions over $\mathbb{Z}_3$ (e.g. $x=y=2 \land w=z=1$ is one of the solutions). Is there any formula for the number of solutions ...
2
votes
1answer
47 views

In how many ways can a number be factorized over the field $\mathbb{Z}_p$ into two numbers?

For example, over the field $\mathbb{Z}_5$, we can factor number 4 into two numbers in three different ways, i.e. 4=4$\times$1, 4=2$\times$2, and 4=3$\times$3. I am looking for a general formula of ...
6
votes
2answers
377 views

Does there exist a prime that is only consecutive digits starting from 1?

This is a problem I came up with the other day, and have absolutely no clue how to solve. The problem is: does there exist a number in the set $K$ that is prime, where $K$ is defined to be the set of ...
3
votes
5answers
6k views

What is the mathematical formula to find the sum of the first 1000 prime numbers?

I am trying to improve my coding skills at codeeval (doing practice problems). One of the programming questions I have to answer is to write code that will sum the first 1000 prime numbers. What is ...
2
votes
0answers
54 views

How to prove that every $l$ (such that $ 2 \leq l \leq \lfloor \sqrt{k^2+2n+1} \rfloor $) divides at least one of the following numbers?

$ k^2+2n, k^2, k^2+1, 2n, 2n+1$, (for some $n$) if $k$ is even and $0 < n < k$. I have no idea of how to prove that. I'm working on Legendre's conjecture. Update 1: Yes, for $n=0$ all $l$ ...
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 ...
2
votes
2answers
341 views

Can an infinite set of primes be a regular language or CFG?

At first glance, it seems like the pumping lemmas should somehow "easily" show that an infinite set of primes (say, written in binary) cannot be a regular language or context-free grammar. But I don't ...
8
votes
1answer
67 views

Existence of root of a polynomial over $\mathbb F_p$.

I came accross the following question and I can't find an easy proof of this fact : Let $p\geq 17$ be a prime number such that $p\equiv 1 \pmod 4$. Show that for any $z\in \mathbb ...
0
votes
2answers
20 views

Relate $n$ with $2$

Suppose $a, b$ and $n$ are positive integers, all greater than one. If $a^n+b^n$ is prime, what can you relate $n$ with 2? My approach: for $a^n+b^n$ to be prime $\forall n>1$, $a$ and $b$ has to ...
2
votes
1answer
55 views

When a quadratic involving three primes is a perfect square

How do we find all primes $p,q,r$ such that $p^2+q^2+rpq$ is a perfect square ? with $r=7$ and $p=q$ we have the expression a perfect square
3
votes
0answers
105 views

Major arcs in the proof that every odd number is the sum of at most 5 primes

In his proof that all odd numbers greater than 1 are the sum of at most 5 primes, Terence Tao uses one large major arc around 0 rather than small ones around the rationals, which I am more accustomed ...
4
votes
1answer
67 views

How to prove that if $c$ >$8/3$ then there exist a real number $\theta $ such that $\bigl\lfloor\theta^{c^n}\bigr\rfloor$ is prime

How to prove that if $c$ >$8/3$ then there exist a real number $\theta $ such that $\bigl\lfloor\theta^{c^n}\bigr\rfloor$ is prime for every positive integer $n$?
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 $ ...
0
votes
2answers
53 views

If $p~ \mid~ m^p + n^p$, prove $p~ \mid~ \frac{m^p + n^p}{m+n}$. [duplicate]

If $p \mid m^p + n^p$, and $p$ is a prime greater than $2$, prove $$p \mid \frac{m^p + n^p}{m+n}.$$ No clue how to start. Clearly $p \mid m + n$, but then what. I feel very less information is given. ...
2
votes
3answers
67 views

Prime number proof

Given that $n>2$. Prove that if $2^n-1$ is prime then $2^n+1$ is composite or vice versa. I looked on wikipedia on Fermat number and Mersenne prime, but I still don't know how they work.
1
vote
0answers
57 views

Proof: There are infinite prime numbers of the form 4k+3 [duplicate]

I have to proof if true or wrong: There are infinite prime numbers of the form 4k+3. I want to proof: Yes, this is true. My ideas: 1) Assume - as a contradiction - that there are only infinite prime ...
1
vote
3answers
1k views

A quick way to determine whether a number is prime by hand [closed]

I need a quick way to determine whether a number is prime by hand. Any suggestions?
16
votes
6answers
22k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?
4
votes
2answers
683 views

Proof of divergence of $1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…$ [duplicate]

What is an elementary proof to the fact that $\frac{1}{p_1} + \frac{1}{p_2} + \frac{1}{p_3} + \dots$ diverges. ($p_i$ denotes the $i$th prime.)
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$ ...
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: ...
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 ...
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 ...
0
votes
1answer
169 views

$a ≡ b $(mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$)

Verify that if $a ≡ b$ (mod $n_1$) and $a ≡ b$ (mod $n_2$), then $a ≡ b$ (mod $n$), where the integer $n = lcm(n_1 , n_2)$. Hence, whenever $n_1$ and $n_2$ are relatively prime, $a ≡ b$ (mod ...
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 ...
1
vote
3answers
116 views

Number of prime numbers in a range

Is there any function to evaluate the number of prime numbers between [2, n]? For example, consider the following range: ...
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 ...
6
votes
2answers
1k views

The Prime Polynomial : Generating Prime Numbers

First of all, i'll confess i'm no math geek. I'm from Stackoverflow, but this question seemed more apt here, so i decided to ask you guys :) Now, i know noone has discovered (or ever will) a ...
2
votes
5answers
210 views

On prime numbers

let $q$ be a prime let $p = 2^q -1 $ is p must be prime always for any prime q ? is this is true always ? or it is false for some prime q ? if it is false , give an example to show that there ...
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 ...
-1
votes
3answers
781 views

Prime number rule [closed]

I was requesting somebody to help me discuss how the prime number rule helps to solve easily the sudoku game in just a few minutes and an example showing the relevant steps on how the rule is used
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 ...
13
votes
1answer
284 views

What is the smallest integer $n$>1 such that $n^{5000}+n^{2013}+1$ is prime?

Which is the smallest integer $n>1$, such that $$n^{5000}+n^{2013}+1$$ is prime ? Since $x^{5000}+x^{2013}+1$ is irreducible over $\mathbb{Q}$ and has value $1$ for $x=0$, there should be ...
4
votes
2answers
785 views

Show for prime numbers of the form $p=4n+1$, $x=(2n)!$ solves the congruence $x^2\equiv-1 \pmod p$. $p$ is therefore not a gaussian prime.

I need to show that for prime numbers of the form $p=4n+1$, $x=(2n)!$ solves the congruence $x^2 \equiv-1\pmod p$. I then need to show this implies p isn't a gaussian prime. I have started to solve ...
0
votes
3answers
261 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.
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 ...
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 ...
1
vote
1answer
279 views

Firoozbakht’s conjecture and Cramér's conjecture

Firoozbakht’s conjecture states, for every prime number: $$\sqrt[{p_{k+1}}]{p_{k+1}}\lt\sqrt[{p_k}]{p_k}$$ for all $n\ge 1$. The Cramer's conjecture states: $$p_{n+1}-p_n=O((\log p_n)^2)$$ The ...
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
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 ...
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
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 ...
7
votes
1answer
157 views

How can prove this $\binom{n}{p}\equiv \left\lfloor\frac{n}{p}\right\rfloor \pmod {p^2}$

Show that if $n \gt p \gt 0$: $$\binom{n}{p}\equiv \left\lfloor\dfrac{n}{p} \right\rfloor\pmod{ p^2}$$ where $p$ is prime. and $$\binom{n}{p}=\dfrac{n!}{(n-p)!p!}$$ This is theorem? True or false? If ...
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, ...
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$ ...
20
votes
4answers
12k views

Simple explanation and examples of the Miller-Rabin Primality Test

Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test. Specifically: I understand that for some reason, having non-trivial ...