wu :: forums - Print Page


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

        riddles >> easy >> Fibonacci number + 77 = 7th power?
        
(Message started by: NickH on Oct 16^th, 2004, 8:12am)

Title: Fibonacci number + 77 = 7th power?
Post by NickH on Oct 16^th, 2004, 8:12am

Show that no Fibonacci number takes the form n⁷ - 77, where n is a positive integer.

Title: Re: Fibonacci number + 77 = 7th power?
Post by Sir Col on Oct 17^th, 2004, 8:29am

I've not solved it completely, but I have made some progress...

::[hide]
Using a spreadsheet to explore the Fibonacci sequence and n⁷ for different modulo bases, I discovered that in base 29 the Fibonacci sequence produces:
1,1,2,3,5,8,13,21,5,26,2,28,1,0,1,1,2,3,...

and n⁷ produces:
1,12,12,28,28,28,1,17,28,17,12,17,28,12,17,1,12,17,...

Clearly the Fibonacci sequence is in a loop and will only be congruent with 1,2,3,5,8,13,21,26,28 mod 29.

Although the spreadsheet seems to suggest so, it is not clear that n⁷ will only be congruent with 1,12,17,28 mod 29. If this is true, n⁷-77 will be congruent with 9,17,22,27 mod 29, and we prove that n⁷-77 will never produce a term in the Fibonacci sequence.

Using Euler's totient function, n^phi(29)=n²⁸==1 mod 29, so (n⁷)⁴==1 mod 29. And sure enough, as values of n⁷ mod 29 can only theoretically be congruent with 0 through 28, it is only for the values 1,12,17,28 that the fourth powers are congruent with 1 (mod 29).

Maybe I am missing the obvious, but I don't see how to connect this yet?! Any ideas?
[/hide]::

Title: Re: Fibonacci number + 77 = 7th power?
Post by Barukh on Oct 18^th, 2004, 1:05am

Sir Col, I don’t see any flaw in your solution. Nice job!

on 10/17/04 at 08:29:25, Sir Col wrote:

Although the spreadsheet seems to suggest so, it is not clear that n⁷ will only be congruent with 1,12,17,28 mod 29.

No, it is clear: it is enough to test every n [le] 14 (why?), and you did more.

Your reduction to the 4-th power modulo 29 is nice. The only thing I can add here is make it more fun and try to find those values without going over every n.

So, we want to find all such n that n⁴ [equiv] 1 mod 29. Write it as (n-1)(n+1)(n²+1) [equiv] 0 mod 29. The first two terms give n=1, n=28. The last one has a pair of solutions n, 29-n (that the solution exists, is discussed here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1078017611;start=0#8)), one of which is even, let say 2k. Then, we have
(2k)² [equiv]-1 mod 29 [equiv] 28 mod 29, therefore k² [equiv]7 mod 29. Fortunately, we observe that 6² [equiv]7 mod 29, which gives the pair (12, 17).

Title: Re: Fibonacci number + 77 = 7th power?
Post by Sir Col on Oct 18^th, 2004, 6:26am

I think you're giving me far more credit than I deserve. I still don't see why n⁷[equiv]1,12,17,28 mod 29 can be confirmed by only considering n[le]14?

Again you offer praise where it is not due: the reduction to the fourth power was a random fumble about which I still don't see the connection to the original problem.

In exploring different bases, and after trying some lower bases with little success, I was drawn to certain bases. My first instinct before I went to the spreadsheet was Euler's totient function, and as a^[phi](n)[equiv]1 mod n, it follows for n being prime, a^p-1[equiv]1 mod p. Being unable to take this any further analytically, I turned to the spreadsheet and I considered p=71 initially, because p-1=70 is a multiple of 7. Without any success here, I then tried p=43 for the same reason, and then p=29. I must confess that I still don't see why this was fruitful; it was just my instincts that suggested I should try them.

Any help here would be greatly appreciated.

Title: Re: Fibonacci number + 77 = 7th power?
Post by rmsgrey on Oct 18^th, 2004, 9:26am

For proving the 7th powers mod 29, you only need to check the powers of 0 to 28 since any higher numbers will be the same (mod 29) as one of them. But, knowing that (-x)⁷=-(x⁷), you only need to calculate 7th powers for 0 to 14 directly - 15 to 28 are -14 to -1 respectively.

Title: Re: Fibonacci number + 77 = 7th power?
Post by Sir Col on Oct 18^th, 2004, 9:47am

Of course! *light goes on*

(a+kb)ⁿ[equiv]aⁿ mod b, because (a+kb)ⁿ=aⁿ+b*f(a,b). And aⁿ[equiv](b-a)ⁿ mod b, for the same reason; that is, n⁷[equiv](29-n)⁷ mod 29.

Thanks, rmsgrey and Barukh.

Now can anyone explain why base 29 proved to be so fruitful, and 43 and 71 did not? Can we determine this analytically.

Title: Re: Fibonacci number + 77 = 7th power?
Post by Rezyk on Oct 18^th, 2004, 11:19pm

on 10/17/04 at 08:29:25, Sir Col wrote:

If this is true, n⁷-77 will be congruent with 9,17,22,27 mod 29

!!

2001⁷-77 mod 29 = 10
2002⁷-77 mod 29 = 11

Title: Re: Fibonacci number + 77 = 7th power?
Post by Sir Col on Oct 19^th, 2004, 12:40am

Good spot, Rezyk; I do seem to have been careless! I don't know where I obtained the list: 9,17,22,27, for congruence with n⁷-77 mod 29!? :-[
n⁷[equiv]0,1,12,17,28 mod 29 (I forgot multiples of 7!)
n⁷-77[equiv]9,10,11,22,27

However, f_n[equiv]0,1,2,3,5,8,13,21,26,28 mod 29, so the solution still holds. *phew*

Title: Re: Fibonacci number + 77 = 7th power?
Post by Barukh on Oct 19^th, 2004, 1:06am

on 10/18/04 at 09:47:28, Sir Col wrote:

Now can anyone explain why base 29 proved to be so fruitful, and 43 and 71 did not? Can we determine this analytically.

That’s a good question… I don’t believe there is an analytical way. But here’s what I know about.

Instead of questioning “which base to try?” we may ask “which base not to try?”. First of all, Sir Col rightly chose among prime numbers p only those that 7 divides (p-1), since other prime numbers have all the possible values {0,…,p-1} as residues of n⁷ (why?). And 29 is the smallest such prime.

In 1971, S. Burr proved an interesting result: if N is a number such that F_n mod N is the whole set {0,…,N-1} (that is, every number is congruent to some F_n modulo N), than N has one of the following six forms: 5^k, 2[cdot]5^k, 4[cdot]5^k, 3^m [cdot]5^k, 6[cdot]5^k, 7[cdot]5^k, 14[cdot]5^k. This immediately excludes from the consideration many composite numbers: 6, 9, 10, 14, 15, 20,… In fact, the smallest composite base that has to be treated is 8. Unfortunately, too many bases produce as n⁷ – 77 residues small numbers 2, 3 or 5…

Hope this helps.

Title: Re: Fibonacci number + 77 = 7th power?
Post by rmsgrey on Oct 20^th, 2004, 8:10am

on 10/18/04 at 09:47:28, Sir Col wrote:

And aⁿ[equiv](b-a)ⁿ mod b, for the same reason; that is, n⁷[equiv](29-n)⁷ mod 29.

I get -aⁿ[equiv](b-a)ⁿ mod b for odd n on the grounds that (-a)⁷=-(a⁷)

Title: Re: Fibonacci number + 77 = 7th power?
Post by Sir Col on Oct 20^th, 2004, 9:27am

Good point! I'd missed the fact that, in the expansion of (b-a)ⁿ, symmetry of the form aⁿ[equiv](b-a)ⁿ mod b only holds for even n.

In which case, I can still see why we only need to consider n[le]14 for n⁷ mod 29; for example, 21⁷[equiv](29-21)⁷[equiv]-8⁷ mod 29.

Title: Re: Fibonacci number + 77 = 7th power?
Post by Brad Sampson on Dec 8^th, 2004, 7:01am

I don't get it.

Title: Re: Fibonacci number + 77 = 7th power?
Post by Barukh on Dec 8^th, 2004, 9:26am

on 12/08/04 at 07:01:17, Brad Sampson wrote:

I don't get it.

You don't get what?

Title: Re: Fibonacci number + 77 = 7th power?
Post by THUDandBLUNDER on Dec 8^th, 2004, 6:57pm

on 12/08/04 at 07:01:17, Brad Sampson wrote:

I don't get it.

Wrong thread!
Try here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=wanted;action=display;num=1092314983).