341??
As the heading says, I am looking for an MI proof only for this:
(its relatively easy otherwise)
p≥3 is an integer and a and b are roots of x2-(p+1)x+1.
Prove that for all natural numbers n, an+bn is not divisible by p.
-
UP 0 DOWN 0 1 10
10 Answers
9x + 1/x =p+1
we need to prove
xn + 1/xn = P(n) ≠p.α
we can show
P(n+3) + P(n) = (P(1)-1)(P(n+2) +P(n-1) ) = pλ
now whenever P(n) ≠p.α ,P(n+3) also does so
hence P(n+3) is true whenever P(n) is true
now P(1) ,P(2) ,P(3) are found to be true
hence P(n) is true for all n
341That is really beautiful da.
This was from goiit.com, formerly an alive site: http://www.goiit.com/posts/list/algebra-let-p-3-be-an-an-integer-and-a-and-b-are-the-roots-of-949809.htm#1060883
9sir is there an alternative solution that doesnt involve MI ?
i am unable to find the relatively easy otherwise solution :P
341Yeah, if you consider the sequence modulo p, you will get that it is periodic with period 8. And none of the 1st 8 remainders are zero. :D
9its surely periodic
and it follows the set (1,-1,2,-1,1,-2)
with period 6
how did u get 8 sir ?
and by what different method
341Oh ok. I didnt check at the time of posting. I may have misremembered it. The goiit post was three weeks ago.
9but sir how did u find it was periodic by other means ?
i found by
P(n) + P(n+3) =0
implies P(n) =P(n+6)
wher P is modulo function
341well you have the recusrion formula for the residues modulo p (refer the goiit post). Then you get the first few terms as 1,-1,2,-1,1,-2 and then if you again get 1, -1 , because of the recursion formula, you know the series is gonna repeat.