Here's a new math puzzle

hyh1048576 · 2003-06-20, 14:35

If f(n) is a fabonacci number, p is a prime and p=1or(-1)(mod10)
Show that p|f(p-1)
If you find a correct way, it will be very easy :D

ET_ · 2003-06-20, 14:40

Quote:

Show that p|f(p-1)

that is...?

Luigi

cheesehead · 2003-06-20, 16:03

Quote:

Originally Posted by ET_

Quote:

Show that p|f(p-1)

that is...?

p divides the (p-1)th Fibonacci number

Jwb52z · 2003-06-20, 19:11

There should be a list of math terms somewhere on here for those of us who don't use them alot. I never remember what in the world "mod" means or what it does.

hyh1048576 · 2003-06-20, 23:11

That means p=10k+1 or 10k-1

wpolly · 2003-06-21, 00:59

When p is =+-3(mod 10)
p|f(p+1).....

hyh1048576 · 2003-06-21, 06:54

Well done!
This is Lemma 1
and then……

:arrow: :arrow: :arrow:

2003-06-22, 22:08

Generally!

A prime number must divide G((p+/-1)/2)
G=Fibonacci, or Lucas number.

Iff p = 1, or 4(mod 5), and p = 1(mod 4) then p must divide F((p-1)/2)
p = 29,41,61,89,101,109,149,181,229,241,269,281,

Iff p = 2, or 3(mod 5) and p= 1(mod 4) then p must divide F((p+1)/2)
p = 13,17,37,53,73,97,113,137,157,173,193,197,233,257,277,293,313,

Iff p = 2,or 3 (mod 5) and p = 3(mod 4) then p must divide L((p+1)/2)
p = 7,23,43,47,67,83,103,107,127,163,167,223,227,263,283,

Iff p = 1, or 4(mod 5), and p = 3(mod 4) then p must divide L((p-1)/2)
p = 11,19,31,59,71,79,131,139,151,179,199,211,239,251,311,

hyh1048576 · 2003-06-23, 12:26

:) :D :D OH!SO IT DOES!!!But how to prove???
PS: I prove my puzzle like this:
As we know,f(n)=(a^n-b^n)/sqrt5,here a=(1+sqrt5)/2,b=(1-sqrt5)/2 are the roots of x^2-x-1=0.
And wpolly said that p|f(p+1) iff p=+-3(mod10)(extend by Binomial theorem,realise that p|iCp+1 when i=2,3,...,p-1)(I hide it so it could be more difficult :) )
So we consider f(p+1)f(p-1),we can prove p|f(p+1)f(p-1) in the same way(p|iCp+1 when p=1,2,...,p-1,p+1,...,2p-1).Hence p|f(p-1) when p=+-1(mod10)

hyh1048576 · 2003-06-26, 04:44

Another puzzle about Fibonacci numbers(quite easy but interesting):
S=arccot(F(1))+arccot(F(3))+arccot(F(5))+arccot(F(7))+......
Then S=? :?
Even a monkey can get the answer(using a calculator :) ).But prove it is more interesting.

wpolly · 2003-06-27, 11:01

Let Ui be a Lucas Sequence with Discriminant d, and p is a prime.

Prove that p|Up-(d|p). ((d|p) is the Legendre Symbol)

This is just a generalization of the original puzzle.

[Edit:I've made a big mistake as hyh1048576 points it out.]

2003-06-20, 14:35	#1
hyh1048576 Jun 2003 2⁶ Posts	Here's a new math puzzle If f(n) is a fabonacci number, p is a prime and p=1or(-1)(mod10) Show that p\|f(p-1) If you find a correct way, it will be very easy :D

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Math-related puzzle links	rogue	Puzzles	1	2007-03-31 23:22
Ramanujan math puzzle cracked at last	Jeff Gilchrist	Math	1	2005-03-24 02:31
Math puzzle	Orgasmic Troll	Math	2	2004-12-13 00:08
math puzzles by Dell (puzzle company)....	ixfd64	Puzzles	0	2004-03-16 00:25
Offtopic: Math Puzzle	Matthes	Puzzles	28	2003-06-19 20:27

2003-06-20, 19:11	#4
Jwb52z Sep 2002 2×3×7×19 Posts	There should be a list of math terms somewhere on here for those of us who don't use them alot. I never remember what in the world "mod" means or what it does.

2003-06-20, 23:11	#5
hyh1048576 Jun 2003 2⁶ Posts	That means p=10k+1 or 10k-1

2003-06-21, 00:59	#6
wpolly Sep 2002 Vienna, Austria 333₈ Posts	When p is =+-3(mod 10) p\|f(p+1).....

2003-06-21, 06:54	#7
hyh1048576 Jun 2003 2⁶ Posts	Well done! This is Lemma 1 and then…… :arrow: :arrow: :arrow:

2003-06-22, 22:08	#8
TTn 5×197 Posts	Generally! A prime number must divide G((p+/-1)/2) G=Fibonacci, or Lucas number. Iff p = 1, or 4(mod 5), and p = 1(mod 4) then p must divide F((p-1)/2) p = 29,41,61,89,101,109,149,181,229,241,269,281, Iff p = 2, or 3(mod 5) and p= 1(mod 4) then p must divide F((p+1)/2) p = 13,17,37,53,73,97,113,137,157,173,193,197,233,257,277,293,313, Iff p = 2,or 3 (mod 5) and p = 3(mod 4) then p must divide L((p+1)/2) p = 7,23,43,47,67,83,103,107,127,163,167,223,227,263,283, Iff p = 1, or 4(mod 5), and p = 3(mod 4) then p must divide L((p-1)/2) p = 11,19,31,59,71,79,131,139,151,179,199,211,239,251,311,

2003-06-23, 12:26	#9
hyh1048576 Jun 2003 2⁶ Posts	:) :D :D OH!SO IT DOES!!!But how to prove??? PS: I prove my puzzle like this: As we know,f(n)=(a^n-b^n)/sqrt5,here a=(1+sqrt5)/2,b=(1-sqrt5)/2 are the roots of x^2-x-1=0. And wpolly said that p\|f(p+1) iff p=+-3(mod10)(extend by Binomial theorem,realise that p\|iCp+1 when i=2,3,...,p-1)(I hide it so it could be more difficult :) ) So we consider f(p+1)f(p-1),we can prove p\|f(p+1)f(p-1) in the same way(p\|iCp+1 when p=1,2,...,p-1,p+1,...,2p-1).Hence p\|f(p-1) when p=+-1(mod10)

2003-06-26, 04:44	#10
hyh1048576 Jun 2003 40₁₆ Posts	Another puzzle about Fibonacci numbers(quite easy but interesting): S=arccot(F(1))+arccot(F(3))+arccot(F(5))+arccot(F(7))+...... Then S=? :? Even a monkey can get the answer(using a calculator :) ).But prove it is more interesting.

2003-06-27, 11:01	#11
wpolly Sep 2002 Vienna, Austria 3·73 Posts	Let Ui be a Lucas Sequence with Discriminant d, and p is a prime. Prove that p\|Up-(d\|p). ((d\|p) is the Legendre Symbol) This is just a generalization of the original puzzle. [Edit:I've made a big mistake as hyh1048576 points it out.]