What is the greatest common factor of all integers of the form p 4 − 1 where p is a prime number greater than 5?
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.
Same method, but I did not consider f ( 7 ) and f ( 1 1 ) , I went straight to the divisibility of 2 , 3 and 5 using similar reasoning to you. May I ask what was the point of considering f ( 7 ) and f ( 1 1 ) ?
We also have to prove that the gcd is not bigger than 240. For this, it is enough to examine the gcd(f(7),f(11))=gcd(2400,14640)=240.
(As the gcd of multiple numbers cannot be greater than the (minimal) gcd of any two of them. In other words, what is not common for any two, cannot be common for all (the whole set)).
I see now, thank you!
By Fermat's Little Theorem, p 4 − 1 ≡ 0 m o d 5 and p 4 − 1 = ( p 2 ) 2 − 1 ≡ 0 m o d 3 . So by the Chinese Remainder Theorem, p 4 − 1 ≡ 0 m o d 1 5 . Furthermore, p 4 − 1 ≡ 0 m o d 1 6 for all odd p , however, this is not true modulo 3 2 , for if p ≡ 3 m o d 3 2 , then p 4 − 1 ≡ 3 4 − 1 ≡ 8 0 ≡ 1 6 m o d 3 2 . Therefore, 1 5 ⋅ 1 6 = 2 4 0 must evenly divide the answer. Since g c d ( 7 4 − 1 , 1 1 4 − 1 ) = 2 4 0 , the answer must be 2 4 0 .
Note that g cd ( 7 4 − 1 , 1 1 4 − 1 ) = 2 4 0 . Since the Carmichael Lambda of 240 is 4, we know that a 4 ≡ 1 ( m o d 2 4 0 ) for any a that is coprime to 240. Thus the answer is 2 4 0
Yes, all the work is hidden away in "Carmichael Lambda of 240 is 4".
Sir, Is there a way to find the largest n for a given λ ( n ) = k ?
I will think about an algorithm when I have a block of free time. At first glance, it does not look like a very difficult task.
To the ChallengeMaster: Not that much work is hidden away in " the Carmichael number of 240 is 4." It follows from Fermat that a 4 ≡ 1 modulo 3 and 5 and one can check in a minute that a 4 ≡ 1 ( m o d 1 6 ) for a = 1 , 3 , 5 , 7 .
Problem Loading...
Note Loading...
Set Loading...
Let f ( p ) = p 4 − 1 = ( p − 1 ) ( p + 1 ) ( p 2 + 1 ) . Note that f ( 7 ) = 2 5 ⋅ 3 ⋅ 5 2 and f ( 1 1 ) = 2 4 ⋅ 3 ⋅ 5 ⋅ 6 1 . We can show that their GCD, 2 4 ⋅ 3 ⋅ 5 = 2 4 0 is actually the GCD of all p 4 − 1 .
Since p is odd, p 2 + 1 is even. Both p − 1 and p + 1 are even, and since they are consecutive even numbers, one is divisible by 4. Thus, f ( p ) is always divisible by 2 4 .
When divided by 3, p leaves remainder 1 or 2. If 1, then 3 ∣ p − 1 and if 2, then 3 ∣ p + 1 so f ( p ) is always divisible by 3. Using the same casework, we can see that f ( p ) is always divisible by 5.