I'm doing some assignments to teach myself cryptology. I am still at the introductory cryptology level, where a lot of it is discrete mathematics, so I believe - and hope - that it is a somewhat simple question for someone in here. It has shown to not be that for me, as it has been holding me prisoner the whole evening and afternoon.
The assignment that is bugging me, contains the following text:
Let A be an invertible $m \times m$ matrix over $\mathbb{Z}_{26}$, where $A=A^{-1}$ and from which it follows that $det(A) \equiv \pm 1$ mod $26$.
Show that there are $736$ $2 \times 2$ matrices $A$ over $\mathbb{Z}_{26}$ for which it holds that $A=A^{-1}$.
Hint: Split the problem into two cases. Consider the problem first modulo $2$, then modulo $13$, and finally use the Chinese Remainder Theorem to get the result modulo $26$.
What I have tried to do:
A lot that have not yielded any results yet... The point where I am at now, is after I have split $det(A) \equiv \pm 1$ mod 26 into: $det(A) \equiv \pm 1$ mod $13$ and $det(A) \equiv \pm 1$ mod $2$.
Afterwards, I have been thinking that since $A=A^{-1}$ means that $A^2=I$, what I need to do is find all cases where:
$\pmatrix{a&b\\c&d}^2=\pmatrix{1&0\\0&1}$
Which means I have the congruences: \begin{align} a^2+bc&\equiv1\\ ab+bd&\equiv0\\ ca+dc&\equiv0\\ cb+d^2&\equiv1\ \end{align}
I have no clue where to go from here though.... Or if what I have been doing so far, is the correct way of doing it, if I want to follow that hint... I hope someone can and will help out, and are willing to shed some light on this.
Thanks (a lot) in advance.