2
votes
1answer
64 views

Proving a statement about prime numbers

Let $p_1,p_2,p_3,\cdots$ be all the primes sorted in an increasing order. Is $p_1p_2p_3\cdots p_i + 1$ is always prime? Why? How can I prove that?
0
votes
1answer
25 views

Let q be a prime and k be a integer greater than 1. Show that if x is an integer such that x^2=x(modq^k) then x=0(modq^k) or x=1(modq^k)

Apologies, the equal signs should be triple horizontals. Considering the or condition in this statement, would I be proving both could be true or two serperate cases? Also, is there some sort of ...
0
votes
0answers
37 views

Prove for each $n\in\mathbb{N}$ there exists a prime $q$ such that $n < q < n! + 1$

I'm trying to prove that for each $n\in\mathbb{N}$ there exists a prime $q$ such that $n < q < n!+1$. I think I need to use the fact that every natural number is the product of one or more ...
0
votes
2answers
57 views

Prove that $a^2 \equiv b^2 \pmod q$ if and only if $a\equiv\pm b \pmod q$ for any prime numbers $q$.

Prove that $a^2 \equiv b^2 \pmod q$ if and only if $a\equiv\pm b \pmod q$ for any prime numbers $q$ homework question, please help.
3
votes
2answers
60 views

Let $x$ be greater than $1$. Prove $x$ is prime if and only if for every integer $y$, either $\gcd(x,y)=1$ or $x\mid y$.

I've been having serious trouble with this problem, The first direction-> Proving x is prime if for every integer y, either gcd(x,y)=1 or x|y doesn't seem too difficult. We know that if gcd(x,y)=1 ...
5
votes
1answer
82 views

Polynomials over $\mathbb N$ generating no primefactors smaller than $p_0$ - methods for proving?

Studying a family of recurrent sequences (generalized from the NSW-numbers) I came to the observation, that certain polynomials (over $\mathbb N$) avoid primefactors below some smallest one. For ...
0
votes
1answer
40 views

GCD's and Proofs

Let p and q be odd primes. Prove that gcd(p + q, p - q) = 2. I have considered EEA to multiply it out, but I'm unsure where to go from there.
0
votes
2answers
78 views

Proving that $\sum_p\frac{1}{p+1}$ diverges

How does one prove $$\sum_{p\in\Bbb P}\frac1{p+1}=\infty.$$ Where $\Bbb P$ denotes the set of prime numbers. I have attempted forming an inequality by playing around with Euler's work on the ...
-2
votes
3answers
75 views

Prove that $S=1+2+3+…+n$ is not a prime number

I need help: I don't know how to prove that $S=1+2+3+\cdots+n$ is not a prime number, for any $ n \ge 3 $. Thank you in advance.
2
votes
2answers
84 views

How to prove a given number is prime?

How would I go about showing a number is prime, especially a very large number. Say I wanted to show that 43112621 is a prime number. How would I go about doing this without showing no other prime ...
0
votes
1answer
103 views

simple proof of a theorem that is weaker than chen's theorem?

I want to see a simple proof of a theorem that is weaker than chen's theorem. Thus let $m,n$ be positive integers. An m-almost prime is a squarefree integer that is the product of at most $m$ primes. ...
4
votes
4answers
285 views

A short or elegant proof for if $p | n^2$ then $p | n$ when $p$ is prime?

Let $n, p \in \mathbb{Z}^{+}$ such that $p$ is prime. Prove $p | n^2 \Rightarrow p | n$. What is a short or elegant proof to this? Some ideas are given at the question Prove that $\sqrt 5$ is ...
1
vote
1answer
55 views

Using Mathematical Induction for a proof

How can I use Mathematical Induction to prove that there are an infinite number of prime numbers?
0
votes
1answer
392 views

Euler's Formula for Primes

Is there any way to prove that the Euler's Formula for Primes $n^2+n+41=41^2$ is valid? How would you even start to prove that a number is prime? If you could prove that a certain number is prime, it ...
3
votes
0answers
43 views

How does Hildebrands proof of the prime number theorem via large sieve work?

How does the sieve inequality (I may not know the most general form) lead to the distribution of primes? To me, these concepts do not seem to be related. Can their connection be described in a ...
11
votes
5answers
2k views

Why does one counterexample disprove a conjecture?

Can't a conjecture be correct about most solutions except maybe a family of solutions? For example, a few centuries ago it was widely believed that $2^{2^n}+1$ is a prime number for any $n$ . For ...
5
votes
2answers
182 views

Proof of the infinitude of primes by probabilistic methods.

I'm looking if there is proof of the infinitude of prime numbers using probabilistic method. I am motivated by the answer of my question here. The answer is based on a relationship between ...
8
votes
1answer
272 views

A simple way to obtain $\prod_{p\in\mathbb{P}}\frac{1}{1-p^{-s}}=\sum_{n=1}^{\infty}\frac{1}{n^s}$

Let $ p_1 <p_2 <\ldots <p_k <\ldots $ the increasing list in set $\mathbb{P}$ of all prime numbers . It is well known (by Infinite geometric series $\sum_{k=0}^\infty r^k = \frac{1}{1-r}$ ...
2
votes
0answers
277 views

Confusing proof of brun's theorem?

I read Brun's proof of Brun's theorem here : http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f110.image (and the following pages) and here http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f138.image ...
3
votes
1answer
118 views

Is my proof correct? $p_1p_2p_3\cdots p_n+1)$ cannot be the square of an integer

Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer. Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so ...
0
votes
1answer
67 views

Proving finite vs infinite representation of $p/q$ in base-$b$?

Reading up on positional notation and converting between different bases, I came across this statement: For integers p and q with gcd(p, q) = 1, the fraction p/q has a finite representation in base b ...
4
votes
1answer
586 views

are two consecutive numbers relatively prime?

I have a question. I have been given this proof: "For any $n$ in the integers where $n>2$, show there are at least $2$ elements in $U(n)$ that satisfy $x^2=1$." I have gone through and actually ...
3
votes
3answers
110 views

Explanation of Zagiers Proof for primes of the form $4k+1$

What is the content of Zagiers proof? What is the actual proof and why does it work? I am not sure I understand why, there is only one fixed point, and why that implies that the involution ...
6
votes
1answer
454 views

Supposed proof of dirichlets theorem on primes

I think theirs somthing wrong with this proof as it was not hard to create, if someone could find a mistake I would greatly appreiciate it: Define a function $[k\equiv b$ mod a], to be equal to zero ...
3
votes
2answers
156 views

Proving A Theorem Concerned With Prime Numbers

I am in the process of reading this brilliant little book Prove It: A Structured Approach--very brilliant, have I mention that already? Anyways, here is the theorem: For every positive integer ...
1
vote
6answers
111 views

help with this assertion: The only number divisible by 3 and that is prime is 3

I have encountered this phrase within a proof by prime numbers and couldn't figure out if it is true. Is there any proof lurking around for this fact? thanks!
5
votes
1answer
191 views

Proving there are infinitely many primes of the form $a2^k+1.$

Fix $k \in \mathbb{Z}_+$. Prove that we can find infinitely many primes of the form $a2^k +1,$ where $a$ is a positive integer. We can use the result that: If $p \ne 2$ is a prime, and if ...
26
votes
1answer
1k views

A prime number pattern

The algorithm Given a natural number $n$ define a procedure as follows: Generate a list of primes upto and possibly including, $n$ Assign $Z = n$ If $Z > 0$, subtract the largest prime from list ...
0
votes
3answers
244 views

How to prove $p$ divides $a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}$ when $p$ is prime, $a, b \in \mathbb{Z}$ and $a,b \lt p$?

If $p$ is a prime number and $a, b \in \mathbb{Z}$ such that $a,b \lt p$, then how could we prove that $p$ divides $\left(a^{p - 2} + a^{p - 3} b + a^{p - 4} b^2 + \cdots + b^{p - 2}\right)$?
3
votes
4answers
135 views

To prove an elementary statement

I have an elementary doubt, Sorry for disturbing you all. I have a statement of this sort. $$r^2-1=p^a(f(p))=(r+1)(r-1). \tag{1}$$ Where $r$ is an even number, and $p$ is an odd prime. $f(p)$ is a ...
0
votes
2answers
199 views

Algebraic Representability of Prime Number Generators

Does anyone happen to have at hand a short, elegant proof that demonstrates that there do (or do not) exist one or more algebraically representable prime number generating functions?
0
votes
2answers
150 views

Proving $2^{\varphi(n)}\ge n$

To show $n\in\mathbb{N}\setminus \{6\}\Rightarrow 2^{\varphi(n)}\ge n$ I can't follow the proof from http://mathematicalspectacles.blogspot.de/2012/05/interesting-study-of-zsigmondy-primes.html ...
0
votes
1answer
140 views

Value $\Phi_n(1)$ of the cyclotomic polynomial at x=1 [duplicate]

Possible Duplicate: Value of cyclotomic polynomial evaluated at 1 I have to show $\Phi_n(1)=1$ for $n\neq p^k$ with $p$ is prime. (I already proved to easy part $\Phi_n(1)=p$ for $n=p^k$) ...
0
votes
0answers
141 views

Infinitely many primes in every row of array?

Friend of mine gave me this problem : Consider the following array of natural numbers : $\begin{array}{ccccccccc} 1 & 2 & 4 & 7 & 11 & 16 & 22 & 29 & \ldots \\ 3 ...
1
vote
2answers
150 views

How to prove that this Proth number cannot be a prime number?

Without using a computer prove that this Proth number cannot be a prime number : $$43373\cdot 2^{49822}+1$$
0
votes
1answer
47 views

How to prove this modular criterion for prime numbers of the form $p=2^n \pm a$?

How to prove following statement : For prime numbers $p$ greater than $3$, it is true that: if $p=2^n-a$ and $a\equiv 1 \pmod 6$ then $p\equiv 1\pmod 3$ if $p=2^n+a$ and $a\equiv 5 \pmod ...
3
votes
2answers
223 views

If $a^n+n^{a}$ is prime number and $a=3k-1$ then $n\equiv 0\pmod 3$?

Is it true that : If $a^n+n^{a}$ is prime number and $a=3k-1$ then $n\equiv 0\pmod 3$ where $a>1,n>1 ; a,n,k \in \mathbb{Z^+}$ I have checked statement for many pairs $(a,n)$ and it ...
14
votes
2answers
598 views

Proof involving induction and primes

I'm looking to prove that: $$p_n \leq 2^{2^{n-1}}$$ Where $p_n$ denotes the $n$th prime in ascending order. The proof method is induction. I've solved my base case, that is: $n=1$ $p_1 = 2$, ...
3
votes
1answer
104 views

Is this proof about the form $2^n \pm a$ correct?

I want to prove following statement : For prime numbers $p$ greater than $3$, it is true that: $a)$ if $p=2^n-a$ and $a=6k+1$, then $n$ is an odd number. $b)$ if $p=2^n+a$ and $a=6k-1$, ...
2
votes
3answers
182 views

Show there is no prime in a range of numbers

How do I show that except for 5039, there is no prime between 5033 and 5047. I just need a nudge in the right direction, no idea how to start the problem :(
1
vote
0answers
71 views

Prime numbers of the form: $k\cdot 2^n \pm 1$ , where $k<3n$

Is it true that : For every $n$ there exists a number $k<3n$ such that: $k\cdot 2^n-1$ or $k\cdot 2^n+1$ is prime,where $k,n\in \mathbf{N}$ Maple code that prints least $k$ such that ...
1
vote
0answers
65 views

Prime numbers of the form : $2^{n+a}+2^{n} \pm 1$ , where $0 \leq a < n$ and $n \equiv 0 \pmod 6$

Is it true that : For any positive integer $n$ such that $n \equiv 0 \pmod 6$ there is at least one prime number of the form: $p=2^{n+a}+2^{n} + 1$ , or , $p=2^{n+a}+2^{n} - 1$ with ...
2
votes
1answer
165 views

If $2^n+n^2$ is prime number then $n \equiv 0 \pmod 3 $?

Is it true that : $((2^n+n^2) \in \mathbf{P} \land n \geq 3)\Rightarrow n\equiv 0 \pmod 3 $ I have checked this statement for the following consecutive values of $n$ : ...
1
vote
1answer
160 views

Infinitely many primes of the $\sum_{i=0}^{a} n^{i}+m\cdot\sum_{i=0}^{b} n^{i}$ form?

How to show that there is infinitely many prime numbers of the form: $p=\sum_{i=0}^{a} n^{i}+m\cdot\sum_{i=0}^{b} n^{i}$ where: $m\in \mathbb{Z}^{*}$ , $a,b,n\in \mathbb{N}$ , $\gcd(a+1,b+1)=1$ For ...
2
votes
1answer
99 views

With what probability is this polynomial equal to zero (mod a prime $p$)?

If we suppose that we have a polynomial $q(x)$ of the following form: $q(x) = \sum_{i=0}^N{c_i x^i} \text{ where } c_i=0 \text{ or } c_i=1$ In other words, if we are given a polynomial with binary ...
2
votes
0answers
298 views

Sum of odd prime and odd semiprime as sum of two odd primes?

How to prove that each sum of odd prime and odd semiprime can be written as sum of two odd primes $(p_1+p_2p_3=p_4+p_5)$ ? Since we know that each prime number greater than $3$ is of the form $6k\pm ...
1
vote
3answers
439 views

Can we use Peano's axioms to prove that integer = prime + integer?

Every integer greater than 2 can be expressed as sum of some prime number greater than 2 and some nonegative integer....$n=p+m$. Since 3=3+0; 4=3+1; 5=3+2 or 5=5+0...etc it is obvious that statement ...
4
votes
2answers
230 views

What's wrong with my proof of infinitely many primes of the form $am+b$, $\gcd(a, b) = 1$

So the prof said in class that the proof of this is hard, but we might want to attempt at home. I won't be able to see him again until Wednesday, but I'm guessing there is some hole in my proof, since ...
2
votes
1answer
207 views

Even numbers greater than 10 as sum of two specific odd numbers

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved(or disproved) ,so my question is: Is it true that every even number ...
2
votes
1answer
594 views

Even numbers greater than 6 as sum of two specific primes

It is well known fact that it is very hard to prove Goldbach's strong conjecture but perhaps some weaker variations can be proved ,so my question is: Is it true that every even number greater than 6 ...