Author 
Topic: Factors of 7^(7^n) + 1 (Read 1344 times) 

Johan_Gunardi
Guest

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

« Last Edit: Feb 21^{st}, 2008, 7:36am by Eigenray » 
IP Logged 



iyerkri
Newbie
Gender:
Posts: 17


Re: Hard Problem!
« Reply #1 on: Jun 16^{th}, 2007, 6:34pm » 
Quote Modify

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


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Hard Problem!
« Reply #2 on: Jun 17^{th}, 2007, 5:54am » 
Quote Modify

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


IP Logged 



iyerkri
Newbie
Gender:
Posts: 17


Re: Hard Problem!
« Reply #3 on: Jun 17^{th}, 2007, 1:28pm » 
Quote Modify

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


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Hard Problem!
« Reply #4 on: Jul 29^{th}, 2007, 5:35pm » 
Quote Modify

This is sort of cheating, but since a=7^{7^n} is 7 times a perfect square, we can do^{*} >Factor[(a^7 + 1)/(a + 1) /. a > 7x^2] (17x+21x^249x^3+147x^4343x^5+343x^6) (1+7x+21x^2+49x^3+147x^4+343x^5+343x^6) [How to discover this by hand, I'm not sure, but it follows from 1a+a^{2}a^{3}+a^{4}a^{5}+a^{6} = (1+a)^{6}  7a(1+a+a^{2})^{2}] Now, it's easily seen that both factors above are > 1, so the ratio (a^{7}+1)/(a+1) is divisible by at least 2 primes, proving the result. Followup: Show that (a^{7}+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 a=p*x^{2}, the polynomial (a^{p}+1)/(a+1) factors over Z iff p=3 mod 4, and (a^{p}1)/(a1) factors iff p=1 mod 4. Why? (Hint: this is actually related to this problem.)

« Last Edit: Jul 29^{th}, 2007, 7:25pm by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Hard Problem!
« Reply #5 on: Feb 21^{st}, 2008, 7:45am » 
Quote Modify

on Jul 29^{th}, 2007, 5:35pm, Eigenray wrote:Followup: Show that (a^{7}+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^{2}, the polynomial (a^{p}+1)/(a+1) factors over Z iff p=3 mod 4, and (a^{p}1)/(a1) factors iff p=1 mod 4. Why? 
 Anybody want to try these? E.g., f(x) = 1 + px^{2} + p^{2}x^{4} + ... + p^{p1}x^{2p2} is irreducible iff p=2 or p=3 mod 4 is prime. (Hint: what (and more importantly, where) are the roots?)


IP Logged 



