sahasumit288's blog

Math,Matrix Power
By sahasumit288, history, 7 years ago, In English

suppose we need to find (a^b)%m. If b is too large we can mode b with phi(m). That means (a^b)%m is equal ( a^ (b%phi(m)) )%m. This theorem works for number properly. Now I have a matrix M two dimensional. Here M^2=M*M,M^3=M*(M^2) and so on.I also mod elements of matrix by m. Suppose that M%m means all elements of matrix are mod by m. Now I need to find (M^b)%m and b is too large. if I mod b by phi(m) will it work? That means (M^b)%m and (M^ (b%phi(m)) )%m will be equal?

Sorry for my bad english and thanks in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Something wrong in this comment.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    Your brute force (or at least the way you implemented it) would not work even in the case of 1x1 matrices (a.k.a. numbers). The result aphi(n) = 1(modn) holds for any a coprime with n. This condition of coprimality makes it hard to extend to the matrix ring.

    On a more particular version of your problem (the case where n is prime), there is one generalization of Fermat's Little Theorem that applies to traces, but not for whole matrices.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I just try to find some number s, such that ab = a(b%s).
      At first i also think, that Ap - 1 = In, but i find that it's wrong for some matrices.

      → Reply