# Tagged Questions

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.$ ...
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 ...
83 views

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 ...
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 ...
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$. ...
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 ...
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 ...
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 ...
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?
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 ...
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.
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 ...
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 ...
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.
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 ...
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.
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 ...
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. ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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}$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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!
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 ...
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 ...
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)$?
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 ...
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?
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 ...
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$) ...
146 views

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 ...
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$, ...
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$, ...
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 :(
### 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 ...
### 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 ...