wu :: forums
wu :: forums - Factors of 7^(7^n) + 1

Welcome, Guest. Please Login or Register.
Sep 18th, 2019, 2:58am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Eigenray, Icarus, towr, Grimbal, SMQ, william wu)
   Factors of 7^(7^n) + 1
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Factors of 7^(7^n) + 1  (Read 1344 times)
Johan_Gunardi
Guest

Email

Factors of 7^(7^n) + 1  
« on: Jun 15th, 2007, 5:26pm »
Quote Quote Modify Modify Remove Remove

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 21st, 2008, 7:36am by Eigenray » IP Logged
iyerkri
Newbie
*





  iyerkri  


Gender: male
Posts: 17
Re: Hard Problem!  
« Reply #1 on: Jun 16th, 2007, 6:34pm »
Quote Quote Modify 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: male
Posts: 2276
Re: Hard Problem!  
« Reply #2 on: Jun 17th, 2007, 5:54am »
Quote Quote Modify 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
*





  iyerkri  


Gender: male
Posts: 17
Re: Hard Problem!  
« Reply #3 on: Jun 17th, 2007, 1:28pm »
Quote Quote Modify Modify

yes!, I should go back to school to learn division by two. Embarassed
IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Hard Problem!  
« Reply #4 on: Jul 29th, 2007, 5:35pm »
Quote Quote Modify Modify

This is sort of cheating, but since a=77^n is 7 times a perfect square, we can do*
 
>Factor[(a^7 + 1)/(a + 1) /. a -> 7x^2]
(1-7x+21x^2-49x^3+147x^4-343x^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
 
1-a+a2-a3+a4-a5+a6 = (1+a)6 - 7a(1+a+a2)2]
 
Now, it's easily seen that both factors above are > 1, so the ratio (a7+1)/(a+1) is divisible by at least 2 primes, proving the result.
 
Followup: Show that (a7+1)/(a+1) is divisible by at least 2 distinct primes, which are different from all previous primes, and conclude that 77^n+1 is divisible by at least 2n+1 distinct primes.
 
 
*More generally, for p an odd prime, and a=p*x2, the polynomial (ap+1)/(a+1) factors over Z iff p=3 mod 4, and (ap-1)/(a-1) factors iff p=1 mod 4.  Why?  (Hint: this is actually related to this problem.)
« Last Edit: Jul 29th, 2007, 7:25pm by Eigenray » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Hard Problem!  
« Reply #5 on: Feb 21st, 2008, 7:45am »
Quote Quote Modify Modify

on Jul 29th, 2007, 5:35pm, Eigenray wrote:
Followup: Show that (a7+1)/(a+1) is divisible by at least 2 distinct primes, which are different from all previous primes, and conclude that 77^n+1 is divisible by at least 2n+1 distinct primes.
...
For p an odd prime, and a=p*x2, the polynomial (ap+1)/(a+1) factors over Z iff p=3 mod 4, and (ap-1)/(a-1) factors iff p=1 mod 4.  Why?

Anybody want to try these?  E.g.,
 
f(x) = 1 + px2 + p2x4 + ... + pp-1x2p-2
 
is irreducible iff p=2 or p=3 mod 4 is prime.  (Hint: what (and more importantly, where) are the roots?)
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board