# How can I prove that there are infinitely many primes?

Prove that there are infinitely many primes using the following factorization for any $x$: $x^4 + x^2 + 1 = (x^2 − x + 1)(x^2 + x + 1)$.

a) Prove that for any even integer $x$, there does not exist a prime number $p$ such that $p \mid (x^2 − x + 1)$ and $p \mid (x^2 + x + 1).$

b) For $n\in \mathbb N$, define $a_n = 2^{2^n+1} + 2^{2^{n}} + 1$. Prove that $a_n$ has at least $n + 1$ distinct prime factors.

c) Use part (b) to prove that there are infinitely many primes

My Solution:

a) So my initial thought is to just prove this using "by way of contradiction". So that turns into the statement saying that there does exist some prime number such that it can divide either equations. We can also replace $x$ with $x = 2k$ for some $k \in \mathbb Z$ since $x$ is even. $p \mid ((2k)^2 - 2k +1)$ which is $p \mid (4k^2 -2k +1)$ or $p \mid (4k^2 + 2k + 1)$. Looking at this statements, I can tell that $p$ will be some odd prime number. So isn't 1 just that prime number $p$? So wouldn't the statement be false because the contradiction is true?

b) I solved this using induction.

c) Pretty straight forward after b) is solved.

• Hint: If $p$ is a factor of both $x^2+x+1$ and $x^2-x+1$, what other numbers is it also a factor of? Commented Mar 7, 2017 at 2:54
• 1 is not a prime number, so no, p is not 1 Commented Mar 7, 2017 at 3:01
• @Michael It would also be a factor of $(x^2 +x +1)(x^2 -x +1)$ Commented Mar 7, 2017 at 3:09
• Hint: If $d$ divides $r$ and $s$, then it divides $r-s$. Commented Mar 7, 2017 at 6:13
• Making any progress, Spencer? Commented Mar 8, 2017 at 11:45

So I managed to figure out a solution thanks to the comments, this is what I have. So proving by way of contradiction. $p \mid (x^2 -x +1)$ and $p \mid (x^2 +x+1)$ so $p \mid ((x^2 + x +1) - (x^2 -x +1))$ which means $p \mid 2x$. 2 is THE lowest prime number since 1 isn't a prime number and since we're saying that $p$ is odd and some prime number, $p$ cannot divide $2$, so it must be able to divide $x$. We can use $p \mid (x^2 -x +1)$ to state that $pk = x^2-x+1$ where $k \in$ Z. Rearrange that to form $\frac{x^2-x+1}{p} = k$ and simplify this to form $k = \frac{x^2}{p} - \frac{x}{p} + \frac{1}{p}$. We already know that $p \mid x$ so $p \mid x^2$ meaning that $\frac{x^2}{p} \in Z$ and $\frac{x}{p} \in Z$. So to satisfy our equation, we need $\frac{1}{p} \in Z$ but that can only occur when $p = 1$ but $p$ has to be a prime number and 1 is not a prime number, therefore we have a contradiction.
• Incidentally, there's a much cleaner way of proving your final assertion: you've established that $p\mid x$ and $p\mid(x^2-x+1)$. Since $p\mid x$, $p\mid x\cdot(x-1)$; in other words, $p\mid(x^2-x)$. Now, since $p\mid (x^2-x)$ and $p\mid (x^2-x+1)$, then using the same trick as you used to find $p\mid x$, we get that $p\mid \left((x^2-x+1)-(x^2-x)\right)$; in other words, $p\mid 1$, which is obviously contradictory. (This is essentially the same argument as yours - just presented in a cleaner way.) Commented May 13, 2019 at 23:53