wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Factors of 7^(7^n) + 1
        
(Message started by: Johan_Gunardi on Jun 15^th, 2007, 5:26pm)

Title: Factors of 7^(7^n) + 1
Post by Johan_Gunardi on Jun 15^th, 2007, 5:26pm

Prove that for every nonnegative integer n, the number 7^(7^n) + 1 is the product of at least
2n + 3 (not necessarily distinct) primes.

//Title changed by Eigenray

Title: Re: Hard Problem!
Post by iyerkri on Jun 16^th, 2007, 6:34pm

[hideb]
By induction. For n=0, 7^(7^n) + 1 = 8 = 2*2*2.

Assume for n. Let 7^(7^n) = a. Then,
7^(7^(n+1)) + 1
= a^7 + 1
= (a+1)(a^6 - a^5 + a^4 - a^3 + a^2 - a +1)

first term is product of 2n+3 prime terms. Second term is even, hence (power of 2)*(odd number). Clearly for n >0, the second term is greater than 4. Thus a^7 is a product of atleast 2n +3 + 2 = 2(n+1) + 3 primes (not necessarily distinct).
[/hideb]

Title: Re: Hard Problem!
Post by Barukh on Jun 17^th, 2007, 5:54am

iyerkri, unfortunately, your solution doesn't work: [hide]the second term is odd, not even, so it remains to be shown it's not a prime number[/hide].

Title: Re: Hard Problem!
Post by iyerkri on Jun 17^th, 2007, 1:28pm

yes!, I should go back to school to learn division by two. :-[

Title: Re: Hard Problem!
Post by Eigenray on Jul 29^th, 2007, 5:35pm

This is sort of cheating, but since a=7^{7^n} is [hide]7 times a perfect square[/hide], we can do^*

>[hide]Factor[(a^7 + 1)/(a + 1) /. a -> 7x^2][/hide]
[hide](1-7x+21x^2-49x^3+147x^4-343x^5+343x^6) (1+7x+21x^2+49x^3+147x^4+343x^5+343x^6)[/hide]

[How to discover this by hand, I'm not sure, but it follows from

[hide]1-a+a²-a³+a⁴-a⁵+a⁶ = (1+a)⁶ - 7a(1+a+a²)²[/hide]

Now, it's easily seen that both factors above are > 1, so the ratio (a⁷+1)/(a+1) is divisible by at least 2 primes, proving the result.

Followup: Show that (a⁷+1)/(a+1) is divisible by at least 2 distinct primes, which are different from all previous primes, and conclude that 7^{7^n}+1 is divisible by at least 2n+1 distinct primes.

^*More generally, for p an odd prime, and [hide]a=p*x²[/hide], the polynomial (a^p+1)/(a+1) factors over Z iff p=3 mod 4, and (a^p-1)/(a-1) factors iff p=1 mod 4. Why? (Hint: this is actually related to [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1169761594]this problem[/link].)

Title: Re: Hard Problem!
Post by Eigenray on Feb 21^st, 2008, 7:45am

on 07/29/07 at 17:35:09, Eigenray wrote:

Followup: Show that (a⁷+1)/(a+1) is divisible by at least 2 distinct primes, which are different from all previous primes, and conclude that 7^{7^n}+1 is divisible by at least 2n+1 distinct primes.
...
For p an odd prime, and a=p*x², the polynomial (a^p+1)/(a+1) factors over Z iff p=3 mod 4, and (a^p-1)/(a-1) factors iff p=1 mod 4. Why?

Anybody want to try these? E.g.,

f(x) = 1 + px² + p²x⁴ + ... + p^p-1x^2p-2

is irreducible iff p=2 or p=3 mod 4 is prime. (Hint: [hide]what (and more importantly, where) are the roots[/hide]?)