True or False:
If a prime number p is not a factor of an even number a but is a factor of a 3 2 + 1 , then p = 6 4 k + 1 for some integer k .
Inspired by “Journey through Genius” by William Dunham
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
So vivid and clear.
Assume a prime p is not a factor of an even number a but is a factor of a 2 + 1 . Then p must odd and in the form of either 4 k + 1 or 4 k + 3 for some integer k . Assume p = 4 k + 3 for some integer k . Then by Fermat's Little Theorem, p is a factor of a p − 1 − 1 = a 4 k + 3 − 1 − 1 = a 4 k + 2 − 1 . But since p is a factor of a 2 + 1 , it is also a factor of ( a 2 + 1 ) ( a 4 k − a 4 k − 2 + a 4 k − 4 − . . . + a 4 − a 2 + 1 ) = a 4 k + 2 + 1 . This means that p is a factor of ( a 4 k + 2 + 1 ) − ( a 4 k + 2 − 1 ) = 2 , which contradicts the assumption that p is not a factor of an even number. Therefore, we reject the assumption that p = 4 k + 3 for some integer k , which means p = 4 k + 1 for some integer k . In summary,
If a prime p is not a factor of an even number a but is a factor of a 2 + 1 , then p = 4 k + 1 for some integer k .
Similarly, assume a prime p is not a factor of an even number a but is a factor of a 4 + 1 . Since a 4 + 1 = ( a 2 ) 2 + 1 , by the theorem above p in the form 4 k + 1 for some integer k , or in the form of either 8 k + 1 or 8 k + 5 for some integer k . Assume p = 8 k + 5 for some integer k . Then by Fermat's Little Theorem, p is a factor of a p − 1 − 1 = a 8 k + 5 − 1 − 1 = a 8 k + 4 − 1 . But since p is a factor of a 4 + 1 , it is also a factor of ( a 4 + 1 ) ( a 8 k − a 8 k − 4 + a 8 k − 8 − . . . + a 8 − a 4 + 1 ) = a 8 k + 4 + 1 . This means that p is a factor of ( a 8 k + 4 + 1 ) − ( a 8 k + 4 − 1 ) = 2 , which contradicts the assumption that p is not a factor of an even number. Therefore, we reject the assumption that p = 8 k + 5 for some integer k , which means p = 8 k + 1 for some integer k . In summary,
If a prime p is not a factor of an even number a but is a factor of a 4 + 1 , then p = 8 k + 1 for some integer k .
Each similar argument introduces a new theorem that increases by powers of two, so that for any n > 1 we can conclude
If a prime p is not a factor of an even number a but is a factor of a 2 n + 1 , then p = 2 n + 1 k + 1 for some integer k .
Therefore, when n = 5 ,
If a prime p is not a factor of an even number a but is a factor of a 3 2 + 1 , then p = 6 4 k + 1 for some integer k .
So the statement in the problem is true .
Note: Euler discovered and used this theorem to quickly find factors of 2 2 5 + 1 (specifically 6 4 1 and 6 7 0 0 4 1 7 ), which disproved Fermat’s conjecture that all numbers in the form of 2 2 n + 1 are prime numbers.
Problem Loading...
Note Loading...
Set Loading...
Consider a as an element of the multiplicative group Z p × of nonzero integers modulo p . We are told that a 3 2 = − 1 in Z p × , and hence the order of a ∈ Z p × is 6 4 . Thus 6 4 must divide the order p − 1 of the group Z p × , and hence p ≡ 1 ( m o d 6 4 ) as required.