It may not seem like it, but you can generalise this to any matrix. Compute the minimal polynomial of the matrix, that is, the least degree polynomial P such th

It may not seem like it, but you can generalise this to any matrix. Compute the minimal polynomial of the matrix, that is, the least degree polynomial P such that P(A) = 0 and the first coefficient is 1. Then, if you want to compute A^n, first compute the polynomial x^n mod P, then plug in A. In this case P(x) = x^2 - x - 1, and any polynomial Q looks like ax + b mod P, so we only have to keep track of two numbers (a,b), instead of the four numbers in the matrix A^n. In general this allows you to reduce the k^2 numbers to k numbers.