Fibonacci numbers: Recall that f_0 ("f sub 0) is 0, and f_1 := 1. Further, we have the recurrence relation f_{n+1} := f_n + f_{n-1}. Since we now understand matrix-multiplication, we now know what it means to compute the 1024-th power of matrix. The HARD HARD way would be to do 1023 multiplications. We'll do it more easily, by repeated-squaring. But since we >>>> only want the last two digits of f_{1024} <<<< we are working too hard. But hard work never stopped US!: We define our "Fibonacci matrix": > M := <<1|1>,<1|0>>; [1 1] M := [ ] [1 0] Let let > M0 := M; [1 1] M0 := [ ] [1 0] So M0 is the [2^0]-th power of M, i.e, is M^1. Now define > M1 := (M0)^2 ; [2 1] M1 := [ ] [1 1] So M1 is M^{2^1} i.e, is M^2. We get the pattern, so let's automate it. Note that "||" is Maple's (that's the CAS [Computer Algebra System] that I am using) concatenation operator. So if k has value 7, then expression "M||7" creates the variable M7. We automate our process and construct: > n := 0 ; n := 0 > n := n+1 ; M||(n+1) := (M||n)^2; n := 1 [5 3] M2 := [ ] [3 2] > n := n+1 ; M||(n+1) := (M||n)^2; n := 2 [34 21] M3 := [ ] [21 13] > n := n+1 ; M||(n+1) := (M||n)^2; n := 3 [1597 987] M4 := [ ] [ 987 610] So this M4 is M^{2^4} = M^{16}. Let's continue: > n := n+1 ; M||(n+1) := (M||n)^2; n := 4 [3524578 2178309] M5 := [ ] [2178309 1346269] > n := n+1 ; M||(n+1) := (M||n)^2; n := 5 [17167680177565 10610209857723] M6 := [ ] [10610209857723 6557470319842] > n := n+1 ; M||(n+1) := (M||n)^2; n := 6 [407305795904080553832073954 251728825683549488150424261] M7 := [ ] [251728825683549488150424261 155576970220531065681649693] So this matrix is the 2^7 power (that is, the 128-th power) of our little M. How close can we get to computing M^(1024) before we have to buy a new computer? > n := n+1 ; M||(n+1) := (M||n)^2; n := 7 M8 := [229265413057075367692743352179590077832064383222590237 , 141693817714056513234709965875411919657707794958199867] [141693817714056513234709965875411919657707794958199867 , 87571595343018854458033386304178158174356588264390370] > n := n+1 ; M||(n+1) := (M||n)^2; n := 8 M9 := [72639767602615659833415769076743441675530755653534070653184546540063470576806357692953027861477736726533858 , 44893845313309942978077298160660626646181883623886239791269694466661322268805744081870933775586567858979269] [44893845313309942978077298160660626646181883623886239791269694466661322268805744081870933775586567858979269 , 27745922289305716855338470916082815029348872029647830861914852073402148308000613611082094085891168867554589] > n := n+1 ; M||(n+1) := (M||n)^2; n := 9 M10 := [7291993184377412737043195648396979558721167948342308637716205818587400148912186579874409368754354848994831816250311893410648104792440789475340471377366852420526027975140687031196633477605718294523235826853392138525 , 4506699633677819813104383235728886049367860596218604830803023149600030645708721396248792609141030396244873266580345011219530209367425581019871067646094200262285202346655868899711089246778413354004103631553925405243] [4506699633677819813104383235728886049367860596218604830803023149600030645708721396248792609141030396244873266580345011219530209367425581019871067646094200262285202346655868899711089246778413354004103631553925405243 , 2785293550699592923938812412668093509353307352123703806913182668987369503203465183625616759613324452749958549669966882191117895425015208455469403731272652158240825628484818131485544230827304940519132195299466733282] ### Whew!... Ok, so we bullied Maple into computing M^(1024) by brute force --and the shame of it is, I only what the LAST TWO DIGITS of each entry, i.e, I want the matrix > LTD := M10 mod 100; [25 43] LTD := [ ] [43 82] # Now let's do the same computation --again using repeated-squaring-- but only keeping track of the last two digits. I'll use "S" to denote these Small matrices. > S0 := M mod 100; [1 1] S0 := [ ] [1 0] > n := -1 ; n := -1 > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 0 [2 1] S1 := [ ] [1 1] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 1 [5 3] S2 := [ ] [3 2] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 2 [34 21] S3 := [ ] [21 13] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 3 [97 87] S4 := [ ] [87 10] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 4 [78 9] S5 := [ ] [ 9 69] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 5 [65 23] S6 := [ ] [23 42] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 6 [54 61] S7 := [ ] [61 93] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 7 [37 67] S8 := [ ] [67 70] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 8 [58 69] S9 := [ ] [69 89] > n := n+1 ; S||(n+1) := (S||n)^2 mod 100 ; n := 9 [25 43] S10 := [ ] [43 82] ## Wait a second, what was our answer previously? > M10; [7291993184377412737043195648396979558721167948342308637716205818587400\ 14891218657987440936875435484899483181625031189341064810479244078947534\ 04713773668524205260279751406870311966334776057182945232358268533921385\ 25 , 4506699633677819813104383235728886049367860596218604830803023149600\ 03064570872139624879260914103039624487326658034501121953020936742558101\ 98710676460942002622852023466558688997110892467784133540041036315539254\ 05243] [4506699633677819813104383235728886049367860596218604830803023149600030\ 64570872139624879260914103039624487326658034501121953020936742558101987\ 10676460942002622852023466558688997110892467784133540041036315539254052\ 43 , 2785293550699592923938812412668093509353307352123703806913182668987\ 36950320346518362561675961332445274995854966996688219111789542501520845\ 54694037312726521582408256284848181314855442308273049405191321952994667\ 33282] > AnswerThatWasReallyHardToCompute := M10 mod 100; [25 43] AnswerThatWasReallyHardToCompute := [ ] [43 82] And yet we have > S10; [25 43] [ ] [43 82] which was trivial to compute. We could compute S10 by hand (no calculator, just paper) in probably 5 or 6 minutes. ================================================================ By the way, we didn't fully answer the question. What is f_{1024}, the 1024-th Fibonacci number? Well, note that [1 1] [ f_2 f_1 ] M = M0 = M^1 = [ ] = [ ] . [1 0] [ f_1 f_0 ] It is easy to see, by the multiplication, that the k-th power of M [I don't mean M^{2^k}; I just mean M^k] is [ f_{k+1} f_k ] M^k = [ ] . [ f_k f_{k-1} ] Now our M10 is M^{1024}, so it equals [ f_1025 f_1024 ] M^1024 = [ ] . [ f_1024 f_1023 ] And our S10 is [25 43] [ ] [43 82] So --and here is a GREAT LINE to use at a party-- you can now say, casually, hand in pocket, "By the way, I was waiting for the bus, and so I computed the LTD --that stands for Last Two Digits, by by the way-- of the one-thousand-and-twenty-fourth Fibonacci number. Took me, oh, I'd say, about 6 minutes, but that was because I didn't have a calculator". And those LTD are: "43". Best Wishes, "Prof. Jonathan" -- Prof. Jonathan LF King Mathematics dept, Univ. of Florida ,