Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
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)$. –  Andres Caicedo Sep 11 '13 at 3:22
    
(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.) –  Andres Caicedo Sep 11 '13 at 3:40
    
What is $F_5$? :-) Is it supposed to be the fifth Fibonacci number? –  Qfwfq Sep 11 '13 at 9:36
    
@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$ –  Konstantinos Gaitanas Sep 11 '13 at 11:37

1 Answer 1

up vote 12 down vote accepted

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

share|improve this answer
    
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$). –  ARupinski Sep 11 '13 at 21:08

Your Answer

 
discard

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.