Tagged Questions

4answers
1k views

Prime number between n and (1+n!)

I am trying to prove that ($\forall \ n\in\mathbb{N}$) there exists a prime number $q$ such that $n < q \le 1 + n!$ I have made a graph with $n=0$ through $n=10$ and found solutions to all of them ...
1answer
20 views

Let x >= 2. Show that if x is not divisible by any positive integer n satisfying 2<= n<=sqrt(x) then x is a prime number.

A proof is required, but I'm not sure how to do it. Could anyone guide me?
5answers
2k views

Is it true that $n^2+3n+13$ is prime for all $n\in\mathbb ℤ^+$?

Prove or disprove the statement: If $n\in\mathbb ℤ^+$, then $n^2+3n+13$ is prime. I am lost here. All I know is that $n$ is greater than or equal to one, since it is a positive integer.
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.$ ...
5answers
796 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 ...
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 ...
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 ...
0answers
106 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$. ...
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 ...
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 ...
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 ...
1answer
71 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?
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 ...
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.
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 ...
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 ...
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.
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 ...
3answers
113 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.
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 ...
1answer
145 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. ...
4answers
330 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 ...
1answer
80 views

Using Mathematical Induction for a proof

How can I use Mathematical Induction to prove that there are an infinite number of prime numbers?
1answer
596 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 ...
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 ...
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 ...
2answers
211 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 ...
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}$ ...
0answers
334 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 ...
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 ...
1answer
68 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 ...
1answer
803 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 ...
3answers
116 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 ...
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 ...
2answers
195 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 ...
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!
1answer
212 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 ...
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 ...
3answers
262 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)$?
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 ...
2answers
249 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?
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 ...
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$) ...
0answers
146 views

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 ...
2answers
675 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$, ...
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$, ...