Author |
Topic: Fibonacci number + 77 = 7th power? (Read 3287 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Fibonacci number + 77 = 7th power?
« on: Oct 16th, 2004, 8:12am » |
 Quote  Modify
|
Show that no Fibonacci number takes the form n7 - 77, where n is a positive integer.
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #1 on: Oct 17th, 2004, 8:29am » |
Quote Modify
|
I've not solved it completely, but I have made some progress...
::
Using a spreadsheet to explore the Fibonacci sequence and n7 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 n7 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 n7 will only be congruent with 1,12,17,28 mod 29. If this is true, n7-77 will be congruent with 9,17,22,27 mod 29, and we prove that n7-77 will never produce a term in the Fibonacci sequence.
Using Euler's totient function, nphi(29)=n28==1 mod 29, so (n7)4==1 mod 29. And sure enough, as values of n7 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?
::
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #2 on: Oct 18th, 2004, 1:05am » |
Quote Modify
|
Sir Col, I don’t see any flaw in your solution. Nice job!
on Oct 17th, 2004, 8:29am, Sir Col wrote:| Although the spreadsheet seems to suggest so, it is not clear that n7 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 n4 [equiv] 1 mod 29. Write it as (n-1)(n+1)(n2+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), one of which is even, let say 2k. Then, we have
(2k)2 [equiv]-1 mod 29 [equiv] 28 mod 29, therefore k2 [equiv]7 mod 29. Fortunately, we observe that 62 [equiv]7 mod 29, which gives the pair (12, 17).
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #3 on: Oct 18th, 2004, 6:26am » |
Quote Modify
|
I think you're giving me far more credit than I deserve. I still don't see why n7[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, ap-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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #4 on: Oct 18th, 2004, 9:26am » |
Quote Modify
|
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)7=-(x7), you only need to calculate 7th powers for 0 to 14 directly - 15 to 28 are -14 to -1 respectively.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #5 on: Oct 18th, 2004, 9:47am » |
Quote Modify
|
Of course! *light goes on*
(a+kb)n[equiv]an mod b, because (a+kb)n=an+b*f(a,b). And an[equiv](b-a)n mod b, for the same reason; that is, n7[equiv](29-n)7 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.
|
| « Last Edit: Oct 18th, 2004, 1:28pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #6 on: Oct 18th, 2004, 11:19pm » |
Quote Modify
|
on Oct 17th, 2004, 8:29am, Sir Col wrote:| If this is true, n7-77 will be congruent with 9,17,22,27 mod 29 |
|
!!
20017-77 mod 29 = 10
20027-77 mod 29 = 11
|
| « Last Edit: Oct 18th, 2004, 11:26pm by Rezyk » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #7 on: Oct 19th, 2004, 12:40am » |
Quote Modify
|
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 n7-77 mod 29!? 
n7[equiv]0,1,12,17,28 mod 29 (I forgot multiples of 7!)
n7-77[equiv]9,10,11,22,27
However, fn[equiv]0,1,2,3,5,8,13,21,26,28 mod 29, so the solution still holds. *phew*
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #8 on: Oct 19th, 2004, 1:06am » |
Quote Modify
|
on Oct 18th, 2004, 9:47am, 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 n7 (why?). And 29 is the smallest such prime.
In 1971, S. Burr proved an interesting result: if N is a number such that Fn mod N is the whole set {0,…,N-1} (that is, every number is congruent to some Fn modulo N), than N has one of the following six forms: 5k, 2[cdot]5k, 4[cdot]5k, 3m [cdot]5k, 6[cdot]5k, 7[cdot]5k, 14[cdot]5k. 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 n7 – 77 residues small numbers 2, 3 or 5…
Hope this helps.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #9 on: Oct 20th, 2004, 8:10am » |
Quote Modify
|
on Oct 18th, 2004, 9:47am, Sir Col wrote:| And an[equiv](b-a)n mod b, for the same reason; that is, n7[equiv](29-n)7 mod 29. |
|
I get -an[equiv](b-a)n mod b for odd n on the grounds that (-a)7=-(a7)
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #10 on: Oct 20th, 2004, 9:27am » |
Quote Modify
|
Good point! I'd missed the fact that, in the expansion of (b-a)n, symmetry of the form an[equiv](b-a)n mod b only holds for even n.
In which case, I can still see why we only need to consider n[le]14 for n7 mod 29; for example, 217[equiv](29-21)7[equiv]-87 mod 29.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Brad Sampson
Guest
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #11 on: Dec 8th, 2004, 7:01am » |
Quote Modify
 Remove
|
I don't get it.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #12 on: Dec 8th, 2004, 9:26am » |
Quote Modify
|
on Dec 8th, 2004, 7:01am, Brad Sampson wrote:
You don't get what?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Fibonacci number + 77 = 7th power?
« Reply #13 on: Dec 8th, 2004, 6:57pm » |
Quote Modify
|
on Dec 8th, 2004, 7:01am, Brad Sampson wrote:
Wrong thread!
Try here.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print