Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 4 down vote accepted

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

share|cite|improve this answer

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 ?

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.