0
votes
1answer
27 views

Largest $k$ such that $(p-k) = \lceil \sqrt{(p-2k) p} \rceil$

Assume $p \in \mathbb P.$ Assume $0<p-2k<p$ and the next square larger than $p(p-2k)$ is $(p-k)^2$. It is trivial to show that $p(p-2k)+k^2$ is a square. Simply $p(p-2k)+k^2 = (p-k)^2.$ ...
5
votes
5answers
789 views

Proof of infinitely many primes, clarification

Proof: The proof is by contradiction. Suppose there are only finitely many primes. Let the complete list be $p_1,p_2,\dots,p_n$. Let $N = p_1p_2 \dots p_n+1$. According to the Fundamental Theorem of ...
3
votes
3answers
83 views

Beginner Proof about Primes

I am interested in understand the proof of infinitely many primes. It seems like quite an easy proof, ( I know there are many but I am referring to the proof that goes as follows); " Suppose there ...
1
vote
0answers
49 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 ...
7
votes
0answers
89 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$. ...
0
votes
2answers
44 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 ...
2
votes
3answers
41 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
2answers
100 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 ...
3
votes
1answer
69 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
2answers
61 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
66 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
88 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
43 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.
1
vote
2answers
85 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
77 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
87 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 ...
1
vote
1answer
142 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
325 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 ...
2
votes
1answer
79 views

Using Mathematical Induction for a proof

How can I use Mathematical Induction to prove that there are an infinite number of prime numbers?
1
vote
1answer
574 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
61 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 ...
12
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
208 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 ...
9
votes
1answer
304 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}$ ...
3
votes
0answers
328 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
776 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
113 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
465 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 \bmod a]$, to be equal to ...
3
votes
2answers
183 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 ...
2
votes
6answers
118 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
209 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 ...
1
vote
3answers
255 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
144 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
246 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?
1
vote
2answers
155 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
149 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
146 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 ...
5
votes
4answers
1k views

On a topological proof of the infinitude of prime numbers.

There is a proof of the infiniteness of prime numbers using Topology. I was only informed of the existence of this proof. They say it's very elegant. One could show how this proof?
2
votes
2answers
158 views

How to prove that this Proth number cannot be a prime number? (without using a computer)

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
227 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
668 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
105 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
185 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 :(
2
votes
0answers
73 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 ...
2
votes
0answers
68 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 ...