I am reading a proof of there are infinitely many primes of the form $4m+3$, but have trouble understanding it. The proof goes like this:    Assume there are finitely many primes, and take $p_k$ to be the largest prime of the form $4m+3$. Let $N_k = 2^2 \cdot 3 \cdot 5 \cdots p_k - 1$, where $p_1=2, p_2=3, p_3=5, \dots$ denotes the sequence of all primes. We find that $N_k$ is congruent to $ 3 \pmod {4}$, so it must have a prime factor of the form $4m+3$, and this prime factor is larger than $p_k$ &mdash; contradiction.  My questions are:   Why is $N_k$ congruent to $3 \pmod{4}$? Why must $N_k$ have a prime factor of the form $4m+3$ if it's congruent to $3 \pmod{4}$?   It seems that those should be obvious, but I don't see it. Any help would be appreciated!
14942
This is the proof from the book:     Theorem. There are infinitely many primes of the form $4n+3$.    Lemma. If $a$ and $b$ are integers, both of the form $4n + 1$, then the product $ab$ is also in this form.  Proof of Theorem: Let assume that there are only a finite number of primes of the form $4n + 3$, say  $$p_0, p_1, p_2, \ldots, p_r.$$ Let $$Q = 4p_1p_2p_3\cdots p_r + 3.$$ Then there is at least one prime in the factorization of $Q$ of the form $4n + 3$. Otherwise, all of these primes would be of the form $4n + 1$, and by the Lemma above, this would imply that $Q$ would also be of this form, which is a contradiction. However, none of the prime $p_0, p_1,\ldots, p_n$ divides $Q$. The prime $3$ does not divide $Q$, for if $3|Q$  then $$3|(Q-3) = 4p_1p_2p_3\cdots p_r,$$ which is a contradiction. Likewise, none of the primes $p_j$ can divides $Q$, because $p_j | Q$ implies $p_j | ( Q - 4p_1p_2\cdots p_r ) = 3$, which is absurd. Hence, there are infinitely many primes of the form $4n +3$.   END  From "however, none of the prime ...." to the end, I totally lost!    My questions:   Is the author assuming $Q$ is prime or is not? Why none of the primes $p_0, p_1,\ldots, p_r$ divide $Q$? Based on what argument?     Can anyone share me a better proof?     Thanks.
6868
Show that if the smallest prime factor $p$ of the positive integer $n$ exceeds $\sqrt[3]{n}$, then $\frac{n}{p}$ must be prime or 1.  I'm stuck trying to prove this. I tried this using contradiction, but I haven't been able to prove it.  My approach:  Let $p$ be the smallest prime factor of the positive integer $n$.  Let $p &gt; \sqrt[3]{n}$  Then we must show that $\frac{n}{p}$ is either a prime number or 1.  We know that $n = pe$ for some $e \in \mathbb{Z}$.  Thus, $\frac{n}{p} = e$  We also know that $p$ > $\sqrt[3]{n}$, so $p^3 &gt; n$, and $p^2 &gt; \frac{n}{p}$  So, assume $\frac{n}{p} = e$ is not prime nor 1, meaning it's a composite number. Let's try to get a contradiction.  If $\frac{n}{p}$ is composite, then $\exists a,b \neq 1: \frac{n}{p} = ab $  Now, here's where I get stuck. What can I do with this info? $\frac{n}{p} = ab $ and $p^2 &gt; \frac{n}{p}$.
2872
This is just a curiosity. I have come across multiple proofs of the fact that there are infinitely many primes, some of them were quite trivial, but some others were really, really fancy. I'll show you what proofs I have and I'd like to know more because I think it's cool to see that something can be proved in so many different ways.  Proof 1 : Euclid's. If there are finitely many primes then $p_1 p_2 ... p_n + 1$ is coprime to all of these guys. This is the basic idea in most proofs : generate a number coprime to all previous primes.  Proof 2 : Consider the sequence $a_n = 2^{2^n} + 1$. We have that  $$ 2^{2^n}-1 = (2^{2^1} - 1) \prod_{m=1}^{n-1} (2^{2^m}+1), $$  so that for $m &lt; n$, $(2^{2^m} + 1, 2^{2^n} + 1) \, | \, (2^{2^n}-1, 2^{2^n} +1) = 1$. Since we have an infinite sequence of numbers coprime in pairs, at least one prime number must divide each one of them and they are all distinct primes, thus giving an infinity of them.  Proof 3 : (Note : I particularly like this one.) Define a topology on $\mathbb Z$ in the following way : a set $\mathscr N$ of integers is said to be open if for every $n \in \mathscr N$ there is an arithmetic progression $\mathscr A$ such that $n \in \mathscr A \subseteq \mathscr N$. This can easily be proven to define a topology on $\mathbb Z$. Note that under this topology arithmetic progressions are open and closed. Supposing there are finitely many primes, notice that this means that the set $$ \mathscr U \,\,\,\, \overset{def}{=} \,\,\, \bigcup_{p} \,\, p \mathbb Z $$ should be open and closed, but by the fundamental theorem of arithmetic, its complement in $\mathbb Z$ is the set $\{ -1, 1 \}$, which is not open, thus giving a contradiction.   Proof 4 : Let $a,b$ be coprime integers and $c &gt; 0$. There exists $x$ such that $(a+bx, c) = 1$. To see this, choose $x$ such that $a+bx \not\equiv 0 \, \mathrm{mod}$ $p_i$ for all primes $p_i$ dividing $c$. If $a \equiv 0 \, \mathrm{mod}$ $p_i$, since $a$ and $b$ are coprime, $b$ has an inverse mod $p_i$, call it $\overline{b}$. Choosing $x \equiv \overline{b} \, \mathrm{mod}$ $p_i$, you are done. If $a \not\equiv 0 \, \mathrm{mod}$ $p_i$, then choosing $x \equiv 0 \, \mathrm{mod}$ $p_i$ works fine. Find $x$ using the Chinese Remainder Theorem.   Now assuming there are finitely many primes, let $c$ be the product of all of them. Our construction generates an integer coprime to $c$, giving a contradiction to the fundamental theorem of arithmetic.  Proof 5 : Dirichlet's theorem on arithmetic progressions (just so that you not bring it up as an example...)  Do you have any other nice proofs?
50742
$\textbf{Question:}$Does there exist an infinite sequence of integers $a_1, a_2, . . . $ such that $gcd(a_m, a_n) = 1 $ if and only if $|m - n| = 1$? $\textbf{My solution:}$Suppose we have a $n$ element sequence that satisfies the condition.say $a_1,\cdots,a_n$. Now take $n-1$ distinct primes that divides none of the elements of this sequence.call the primes $p_1,\cdots,p_{n-1}$ Then the sequence $a_1p_1,\cdots,a_{n-1}p_{n-1},a_n$ also satisfies the condition. Now,simply take $a_{n+1}=p_1....p_{n-1}$. Then $a_1p_1,\cdots,a_{n-1}p_{n-1},a_n,a_{n+1}$ satisfies the condition.Hence,we can always increase the size of the sequence. In addition $a,b$ with $(a,b)=1$ is a two element sequence that satisfies the condition.Hence we can form an infinite sequence that satisfies the given conditions. If there is any flaw in my argument do tell me.
116479
Prove that if $p$ and $p+2$ are both prime integers greater than $3$, then $6$ is a factor of $p+1$.  Computing a few primes greater than $3$ modulo $6$ shows the following pattern $5,1,5,\dots$ Thus $$\begin{cases}p\equiv1,5 \pmod{6} \\ p+2 \equiv3,7 \equiv3,1 \pmod{6}\end{cases}$$ Also $p+1 \equiv 2,6 \equiv2,0 \pmod{6}$. I'm not sure how to continue from here... I would like to use modular arithmetic to show this. Is it necessary to remember that every prime can be written as $6n+1$ or $6n+5$ here?
83266
For any positive integer $n$, let $\mathrm{PF}(n)$ denote the set of all distinct prime factors of $n$ (not counted with multiplicity).  The question (using the above notation) is: Is it true that for any two positive integers $m$ and $n$, $\phi(mn)=m\phi(n)$ if and only if $\mathrm{PF}(m) \subseteq \mathrm{PF}(n)$, where $\phi$ is the totient function?  Hint for the if direction: Any prime factor of $mn$ must either be a prime factor of $m$ or a prime factor of $n$ (by Euclid's lemma). But since any prime dividing $m$ also divides $n$, $mn$ has the same distinct prime factors as $n$, and hence any integer coprime to one of them is also coprime to the other.  Note that it is possible for $\mathrm{PF}(m) \subseteq \mathrm{PF}(n)$ to be true while $m \not\mid n$. For example, $4 \not\mid 2$, but they both have $2$ as the only prime factor. In this case, $\phi(8)=4=4 \cdot 1=4\phi(2)$.
10396
My coach said that for all positive integers $n$, $n^4+4^n$ is never a prime number.  So we memorized this for future use in math competition.  But I don't understand why is it?
108016
$p \gt 2$ is a prime, then  there are infinite primes $q$  such that $q$  is a quadratic residue modulo $p$.  With , the problem is  easy! How about  Without the use of the theorem? Can one find  an elementary proof?    p.s.  there are  several  elementary ways(without Dirichlet) to show that there are infinite primes $q$  such that $q$  is a quadratic non-residue modulo $p$  Proof 1  The least $q&gt;0$ quadratic non-residue modulo $p$  is a prime . Consider   $$a_0=q, a_1=q+p,a_2=q+pa_1,a_3=q+pa_1a_2,\dotsc, a_n=q+pa_1a_2\dotsb a_{n-1},\dotsc $$ then $(a_i,a_j)=1$  Proof 2  Only $\dfrac{p-1}2$ quadratic non-residues modulo $p$, so there is a integer $a$ such that $(\dfrac{a^2+1}p)=-1$.   In not, only finite $q_1,q_2,\dotsc, q_n$. then there exists $k\in\Bbb Z$ such that $kq_1q_2\dotsb q_n \equiv a \pmod p$. Consider   $$ (kq_1q_2\dotsb q_n)^2 +1$$
41301
Suppose $p$ is a prime number such that $(p-1)/4$ and $(p+1)/2$ are also primes. Show that $p=13$.   My approach:   Since $p$ is prime, it is of the form $6k+1$ or $6k-1$. Now if $p$ is of the form $6k-1$ then $(p+1)/2 = 3k$ which is not possible as $3|3k$.   So $p$ is of the form $6k+1$. Now $(p-1)/4 = 3k/2$ so $2\mid k$. So $p$ is of the form $12k+1$. But now, how to prove $k=1$?  Please help!
98749
I had my own proof for it but I really don't like it (it feels not intuitive at all because it requires factoring!) and I feel there must be a more direct way to do it by a different counting argument.  If anyone has one it would be greatly appreciated!  My "proof":  Recall:  $\phi(N) = $ the number of elements that are relatively prime to $N$ (i.e. have a mod inverse)  $N = pq$ where $p$ and $q$ are prime.  Let's count the number of elements between $1$ to $N-1$ that are NOT relatively prime to $p$ and $q$. Those elements must have at least $p$ or $q$ as one of its factors. So let include all number that have $p$ as a factor and $q$ as a factor and are in the given range.  thus:  $0p, 1p, 2p, ..., kp, ..., p(q-1)$  and  $0q,1q,2q,...,jq,...,q(p-1)$  That gives a count of:  $N - p - q + 1 = pq - p - q + 1 = (p -1)(q-1)$  QED as required.  The reason I am not happy with this argument is that it seems to me there should be a clear intuitive way of doing it without having to factor or substitute the definition of $N$. This seems clear because multiplying $(p-1)$ by $(q-1)$ seems to be a very cute formula and it I would be surprise that its a coincidence because $(p-1)$ and $(q-1)$ also have clear interpretations. I am looking for a more intuitive clear reasoning, because it seems evident from the form of the formula that it should exist.
104287
Show there are infinitely many primes that are equivalent to $1 \pmod{8}$.  Hello there! I have been trying to do this problem for a pretty long time with no avail.    I noticed that this is really similar to Euclid's proof that there are infinitely many primes.  However, I can't find a way to use that here.  Can anyone help me?
74256
(surprisingly, it appears that this question has not been asked before)  Let $\pi(n)$ denote the number of primes $\leq n$. The prime number theorem states that   $$\pi(n) \sim \frac{n}{\log n} \  \text{as}  \ n \to +\infty$$  After painstakingly reading through Erdos's elementary proof of this theorem, I think I understand the mechanics of it from a formal perspective. However, I still don't seem to understand intuitively why this theorem is true. I would like some intuitive insight as to why this theorem holds.   I understand that for a result as deep as this one, even the intuition is going to contain some nitty-gritty details.  It's probably not the sort of thing that you could explain to a child, for example. Nevertheless, I will ask this question regardless. There has to be some convincing argument for this theorem beyond the technical details of the proofs.
84012
I need help with this question: There are infinitely many prime numbers $p$ for which $p + 2$ and $p + 4$ are also primes.  Where should I start? what proof techniques will be useful?  Any input will be very useful to me.
5562
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 Arithmetic, $N$ must be divisible by some prime. This must be one of the primes in our list. Say $p_k \mid N$. But $p_k\mid p_1\dots p_n$, so $p_k\mid(N-p_1 \dots p_n) = 1$ Hence contradiction.  I don't see how this proof works. I understand that $N$ isn't necessarily prime, but I don't understand how it apparently must show that some primes weren't in our list. A number could be made of different powers of the given primes right?  Someone please explain.
94343
Has anyone ever proven that there exists a proof or disproof that there are finitely many Fermat primes. I know that it's an unsolved problem whether there are finitely or infinitely many Fermat primes but my question is only whether it has been proven to be possible to prove or disprove it. If so, how can I access such a proof?
99119
I'm trying to understand some particulars of the following proposition: First, let me write down the theorem on which the subsequent proposition relies.  Theorem. (Euclid). There are infinitely many primes.   Proof: Suppose that there are finitely many primes, say, $p_1, p_2, \ldots, p_n$. Consider $$m=p_1 p_2 \cdots p_n$$ Consider $$m=p_1 p_2 \cdots p_n+1\ge 2$$   By the Fundamental Theorem of Arithmetics, $m$ is a product of primes. Thus $p_k \mid m$ for some $1\le k \le n$. Since $p_k\mid m$ and $p_k\mid p_1 p_2 \cdots p_n$, we have that $p_k \mid (m-p_1 p_2 \cdots p_n)$, i.e. $p_k\mid 1$, which leads to a contradiction. Thus there are infinitely many primes.  $$$$  Proposition: For $n\in\mathbb{N}$, we have $p_n\le 2^{2^n}$, where $p_n$ is the $n$-th prime number. The proof by induction goes as follows. For $k=1$, we have $p_1 = 2\le 2^2=4$. Suppose that the result holds for $1\le k \le n$ . We have seen in the proof of the Theorem above that   $$p_{n+1}\le p_1p_2\cdots p_n+1$$   Thus, by our induction hypothesis,   $$p_{n+1}\le 2^{2^1} 2^{2^2}\cdots 2^{2^n}+1=2^{2^{n+1}-2}+1\le 2^{2^{n+1}}$$   By induction, proposition holds.  What I don't seem to get is how it follows from the Theorem above that $$p_{n+1}\le p_1p_2\cdots p_n+1$$ Moreover, how can one immediately see (other than by proof by induction) that $2^1 + 2^2 + \cdots + 2^n = 2^{n+1}-2$? Would appreciate some clarifications.
52019
After some trials, I found out that a prime $p \gt 5$ is congruent to $q\pmod{30}$, where $q$ is also a prime, and $1 \le q \lt 30 \;$ (i.e.  $p \equiv q\pmod{30}.$  Is there a way to write a formal proof to show this?  Is that an acceptable answer.