# Infinite number of primes

This is an axiomatic proof, but I don't know how to start the exercise

first one, I have to proof that if $q$ divides $a^p-1$ then $q$ divides $a-1$ or $q=2pt+1, t\in \mathbb{Z}$, and, if $q$ divides $a^p+1$ then $q$ divides $a+1$ or $q=2pt+1, t\in \mathbb{Z}$.

Then I have to proof than there exists infinite primes $q$ such that $q=2pt+1$.

And finally I have to prove that if $n>0$ integer, then the prime divisors from $2^{2^n}+1$ are of the form of $2^{n+1}t+1, t \in \mathbb{Z}$

I have tried and tried but I can't begin

-
Are you familiar with the concept of the order of $a$ modulo a prime $p$. Or Fermat's (little) Theorem? – André Nicolas Nov 13 '12 at 2:26
yes but... what can I do with this concepts!!! – Elmo goya Nov 13 '12 at 3:28
If no one answers for a while, I will type out an answer for at least some of the parts. – André Nicolas Nov 13 '12 at 3:31

Let $p$ and $q$ be odd primes. Let $d$ be the order of $a$ modulo $q$. (Since $q$ divides $a^p-1$, the number $a$ cannot be divisible by $q$.)

By Fermat's Theorem, $a^{q-1}\equiv 1\pmod{p}$. So $d$ divides $q-1$.

We are told that $q$ divides $a^p-1$. So $a^p\equiv 1\pmod{q}$, and therefore $d$ divides $p$.

That leaves two possibilities: (i) $d=1$ and (ii) $d=p$.

If $d=1$, then $q$ divides $a-1$, which is one of the given alternatives in the problem.

If $d=p$, then since $d$ divides $q-1$, we have $q-1=ps$ for some integer $s$. But since $q$ is odd, $q-1$ is even, and therefore $s$ is even. Let $s=2t$. We get $q-1=2tp$ and therefore $q=2tp+1$.

In the second problem, we are given that $q$ divides $a^p+1$. So $q$ divides $(a^p+1)(a^p-1)$, that is, $q$ divides $a^{2p}-1$. Like before, let $d$ be the order of $a$ modulo $q$. Then $d$ divides $q-1$ and $d$ divides $2p$. That leaves the possibilities $d=1$, $d=2$, $d=p$, and $d=2p$.

If $d=1$, then $a\equiv 1\pmod q$. This contradicts the fact that $a^p+1\equiv 0\pmod{q}$. If $d=2$, then $a\equiv -1\pmod{q}$, that is, $q$ divides $a+1$, which is one of our allowed conditions.

If $d=p$, then since $d$ divides $q-1$, we conclude as before that $q-1=ps$ for some integer $s$, and as before conclude that $s=2t$ for some integer $t$, giving $q=2pt +1$. If $q=2p$, we get the same conclusion, without even having to go through $s$.

The argument for $2^{2^n}+1$ is of a not very dissimilar character. It is being left to you for a while.

The infinitely many primes part: The argument below is close in spirit to the "Euclid" argument that there are infinitely many primes. Let $p$ be a fixed odd prime. We show there are infinitely many primes of the form $2pt+1$.

Let $p_0,p_1,\dots,p_k$ be all the primes up to $p_k$, including $2$. Let $a=p(p_0p_1\cdots p_k)$.

Consider $a^p-1$. This is equal to $(a-1)(a^{p-1}+a^{p-2}+\cdots +1)$.

Let $q$ be a prime divisor of $a^{p-1}+a^{p-2}+\cdots+1$. Note that $q$ divides $a^p-1$. Note also that $q$ cannot be any of the $p_i$, $i=0$ to $k$. We show that $q$ cannot divide $a-1$. For if it does, then $a\equiv 1\pmod q$. But then $a^{p-1}+a^{p-2}+\cdots +1\equiv p\pmod{q}$, since there are $p$ terms in the sum. But the sum is divisible by $q$, and therefore $q$ divides $p$, and therefore $p=q$. This is impossible, since $p$ divides $a$.

Thus, by the first result proved above, $q$ is of the form $2pt+1$. So for any collection $p_0,p_1,\dots,p_k$ of primes, we have produced a prime of the right shape which is not in that collection. That shows there must be infinitely many primes of the shape $2pt+1$.

-

You can use the fact that $a^n-b^n = (a - b) \times \sum_{i=0}^{n-1}a^ib^{n-1-i}$, and that every natural number has finitely many divisors.

Edit: And I think you mean $\exists t \in \mathbb{Z}, q = 2pt + 1$, right ?

-
I used it, but I don't know what must I do to guarantee that $q=2pt+1$ – Elmo goya Nov 13 '12 at 2:05

I tried proving last part, but I cant complete it also. Anyway, here are the steps that Ive done.

Assume that $p$ is a prime divisor of $2^{2^n}+1$ and let $d$ be the order of $2 \pmod{p}$. Then $2^{2^n}\equiv -1\pmod{p}$. Hence (by squaring both sides), we get $2^{2^{n+1}}\equiv 1\pmod{p}$.

Claim: $d=2^{n+1}$. (To be settled if it is true)

Assuming that the claim is true, we have the following arguments. Certainly, $\gcd(2,p)=1$. So by Fermat's Theorem, $2^{p-1}\equiv 1\pmod{p}$. Hence, $d|p-1$. Thus, $2^{n+1}|p-1$. Hence, there exists a positive integer $t$ such that $p-1=2^{n+1}t$ and the result follows.

-
One thing for sure is that $d|2^{n+1}$ so that $d\le 2^{n+1}$ of which I wanted to show that $d< 2^{n+1}$ is not possible and the claim makes sense. – juniven Nov 13 '12 at 8:26