Of all integers? That's impossible!

What is the greatest common factor of all integers of the form p 4 1 p^4 - 1 where p p is a prime number greater than 5?


The answer is 240.

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.

3 solutions

Discussions for this problem are now closed

Let f ( p ) = p 4 1 = ( p 1 ) ( p + 1 ) ( p 2 + 1 ) . f(p) = p^4 - 1 = (p - 1)(p + 1)(p^2 + 1). Note that f ( 7 ) = 2 5 3 5 2 f(7) = 2^5 \cdot 3 \cdot 5^2 and f ( 11 ) = 2 4 3 5 61. f(11) = 2^4 \cdot 3 \cdot 5 \cdot 61. We can show that their GCD, 2 4 3 5 = 240 2^4 \cdot 3 \cdot 5 = 240 is actually the GCD of all p 4 1. p^4 -1.

Since p p is odd, p 2 + 1 p^2 + 1 is even. Both p 1 p-1 and p + 1 p+1 are even, and since they are consecutive even numbers, one is divisible by 4. Thus, f ( p ) f(p) is always divisible by 2 4 . 2^4.

When divided by 3, p p leaves remainder 1 or 2. If 1, then 3 p 1 3|p-1 and if 2, then 3 p + 1 3|p+1 so f ( p ) f(p) is always divisible by 3. Using the same casework, we can see that f ( p ) f(p) is always divisible by 5.

Same method, but I did not consider f ( 7 ) f(7) and f ( 11 ) f(11) , I went straight to the divisibility of 2 2 , 3 3 and 5 5 using similar reasoning to you. May I ask what was the point of considering f ( 7 ) f(7) and f ( 11 ) f(11) ?

Tai Ching Kan - 5 years, 7 months ago

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

Zee Ell - 5 years, 6 months ago

I see now, thank you!

Tai Ching Kan - 5 years, 6 months ago
Jason Martin
Nov 21, 2015

By Fermat's Little Theorem, p 4 1 0 m o d 5 p^4-1 \equiv 0 \mod 5 and p 4 1 = ( p 2 ) 2 1 0 m o d 3 p^4-1=(p^2)^2 -1 \equiv 0 \mod 3 . So by the Chinese Remainder Theorem, p 4 1 0 m o d 15 p^4-1 \equiv 0 \mod 15 . Furthermore, p 4 1 0 m o d 16 p^4-1 \equiv 0 \mod 16 for all odd p p , however, this is not true modulo 32 32 , for if p 3 m o d 32 p \equiv 3 \mod 32 , then p 4 1 3 4 1 80 16 m o d 32 p^4-1 \equiv 3^4-1 \equiv 80 \equiv 16 \mod 32 . Therefore, 15 16 = 240 15 \cdot 16 =240 must evenly divide the answer. Since g c d ( 7 4 1 , 1 1 4 1 ) = 240 gcd(7^4-1, 11^4-1)=240 , the answer must be 240 240 .

Otto Bretscher
Nov 13, 2015

Note that gcd ( 7 4 1 , 1 1 4 1 ) = 240 \gcd(7^4-1,11^4-1)=240 . Since the Carmichael Lambda of 240 is 4, we know that a 4 1 ( m o d 240 ) a^4\equiv {1}\ \pmod{240} for any a a that is coprime to 240. Thus the answer is 240 \boxed{240}

Moderator note:

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 \lambda (n) = k ?

Krutarth Patel - 5 years, 7 months ago

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.

Otto Bretscher - 5 years, 6 months ago

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 a^4\equiv 1 modulo 3 and 5 and one can check in a minute that a 4 1 ( m o d 16 ) a^4\equiv 1 \pmod{16} for a = 1 , 3 , 5 , 7. a=1,3,5,7.

Otto Bretscher - 5 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...