6
$\begingroup$

The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it:

Problem 19.5 (p. 224) asks:

Use the equations

$641 = 5^4+2^4 = 5\cdot 2^7+1$

to show that 641 divides $F_5$.

Now the latter expression is related to Euler's proof of his Theorem 8 in E134 and the ideas contained in the proof of that theorem is simple enough to lead to 641 being a candidate divisor of $F_5$ which can then be easily checked by hand/calculator.

However, the fact that Stewart includes the other expression as well intrigues me; I have been trying to use factorizations via sums of two squares to see how this expression might arise; for example since \[ F_5 = 65536^2+1^2 = 62264^2+20449^2 \] one can find this factor as \[ 641 = \gcd(65536*62264-1*20449, 65536*20449+1*62264) \]

But this approach is unsatisfactory since

1). Stewart does not mention the latter decomposition of $F_5$ as a sum of two squares

2). This approach makes no use of the decomposition of the potential factor as a sum of two squares/fourth powers

So, does anyone else have a clue as to what theorem/approach Stewart may have intended by including this decomposition. In particular, are there other less well-known theorems dealing with factoring Fermat numbers by expressing potential factors as Generalized Fermat numbers or some other similarly out of the hat approach? Or did Stewart include this expression for no good reason (which seems doubtful given the clarity of the approaches he takes throughout the rest of the book)?

BTW: As to why this is posted here, although the question asked in the book is certainly not research level, the intricacy of the other methods used to demonstrate 641 is a candidate factor indicate that if there is indeed a way to use the decomposition $5^4 + 2^4$ to factor $F_5$, such a method likely involves some deeper mathematics that is/was research-level.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ This is exercise 7 in section 1.5 of Nathanson's Elementary methods in number theory: $F_5=2^{2^5}+1=(2^{32}+5^4\cdot 2^{28})-(5^4\cdot 2^{28}-1)=$ $2^{28}(2^4+5^4)-(5^2\cdot2^{14}+1)(5\cdot 2^7+1)(5\cdot 2^7-1)$. $\endgroup$
    – Andrés E. Caicedo
    Commented Sep 11, 2013 at 3:22
  • $\begingroup$ (The trick dates back at least to Hardy & Wright, it appears at the beginning of section 2.5 in An introduction to the theory of numbers. It may be due to them, as there is no additional attribution.) $\endgroup$
    – Andrés E. Caicedo
    Commented Sep 11, 2013 at 3:40
  • $\begingroup$ What is $F_5$? :-) Is it supposed to be the fifth Fibonacci number? $\endgroup$
    – Qfwfq
    Commented Sep 11, 2013 at 9:36
  • 1
    $\begingroup$ @Qfwfq $F_5$ is the sixth Fermat number. Numbers of the form $F_n=2^{2^{n}}+1$ are called Fermat numbers. Fermat believed that all of them were primes because they satisfy $F_n$ divides $2^{F_n}-2$. But this is incorrect because $F_5$ is a multiple of $641$ $\endgroup$
    – Konstantinos Gaitanas
    Commented Sep 11, 2013 at 11:37

1 Answer 1

Reset to default
12
$\begingroup$

There is no deep mathematics involved here. The proof goes as follows (see, for example, W.A. Coppel, Number Theory: An Introduction to Mathematics, Springer, 2009, p. 160). Since $641=5\cdot2^7+1$ $=5^4+2^4$, we have $5\cdot 2^7\equiv -1 \;(\mathrm{mod}\; 641)$ and $2^4\equiv -5^4 \;(\mathrm{mod}\; 641)$. Thus $$2^{32}=2^4\cdot 2^{28}\equiv -5^4\cdot 2^{28}=-(5\cdot 2^7)^4\equiv -(-1)^4=-1 \;(\mathrm{mod}\; 641).$$

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Ahh... so the usefulness of this particular decomposition is reliant on the happy coincidence that the $5^4$ term corresponds directly with the coefficient 5 appearing in the Proth prime expression of 641. So I guess it doesn't really give much in the way of factoring insights in general (for example there is no similar trick for either of the factors of $F_6$). $\endgroup$
    – ARupinski
    Commented Sep 11, 2013 at 21:08

You must log in to answer this question.

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