1
$\begingroup$

I am reading Elementary Number Theory with Programming, and bump into the proof of "The Fermat numbers $F_n$ and $F_m$ where m ≠ n are relatively prime.":

Theorem: The Fermat numbers $F_n$ and $F_m$ where m ≠ n are relatively prime.

Proof: Let n > m and let d = gcd($F_n$, $F_m$). Since $F_n$ and $F_m$ are odd, it follows that d is odd. We will show that d = 1. Let x = $2^{2^{m}}$ and let a = $2^{n−m}$. Then $F_n$ −2 = $2^{2^{n}}$ −1 = $x^a$ −1. Since a is even, x = −1 is a root of the equation $x^a$ − 1 = 0, implying that x + 1 | $x^a$ − 1. Then $F_m$| $F_n$− 2. Since d | $F_m$, it follows that d | $F_n$ − 2. Now, since, in addition, d | $F_n$, we have d | 2, implying that d = 1 since d is odd, and the proof is over.

I can understand all except the following words:

Since a is even, x = −1 is a root of the equation $x^a$ − 1 = 0, implying that x + 1 | $x^a$ − 1.

How is "x + 1 | $x^a$ − 1" concluded?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Hint. $x^2-1 = (x-1)(x+1)$ and $x^2 - 1 \mid x^{2n} -1$.

$\endgroup$
2
  • $\begingroup$ I still can't figure out why "x = −1 is a root of the equation $x^a$ − 1 = 0" can deduce "x + 1 | $x^a$ - 1". What is the relationship between these 2 statements. $\endgroup$
    – Nan Xiao
    Jan 26, 2018 at 9:17
  • $\begingroup$ Well, if $b$ is a root of a polynomial $P$, then $X-b$ divides $P$. Indeed, do the Euclidian division, $P = Q(X-b) + R$, with $d(R) < d(X-b) = 1$, that is $d(R) = 0$. Since $P(b) = 0$, $R = 0$. $\endgroup$
    – J.-E. Pin
    Jan 26, 2018 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .