Can we find element of order $q^2-1$ in $\text{GL}_2(\mathbb{F}_q)$? How to find element of order $q^2-1$ in $\text{GL}_2(\mathbb{F}_q)$? I am hoping to find field $\mathbb F_{q^2}$ as subalgebra of $2\times 2$ matrices over field $\mathbb F_q$ where $q$ is power of prime number. I was trying with element $\pmatrix {n&1 \\ 1&0}$ but it works only for $q=2,3,4,8,16$. 
It is suggested that this is duplicate of question 
$GL_n(\mathbb F_q)$ has an element of order $q^n-1$
But I don't know how to find $\mathbb F_{q^2}$ in $M_2(\mathbb F_q)$.
Here is test in GAP for above matrix - $n$ is generator of the field multiplicative group.
gap> List([2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41],
>         k->Order([[Z(k),1],[1,0]]*Z(k)^0));
[ 3, 8, 5, 12, 16, 9, 20, 24, 28, 17, 16, 40, 22, 52, 56, 20, 64, 31, 76, 40 ]

To give my motivation - I want to prove that algebra  $M_2(\mathbb F_q)$ can be represented as ${a+bj}$ for $a,b$ belonging to $\mathbb F_{q^2}$ and multiplication given by Cayley-Dickson
$$(a+bj)(c+dj)=ac+\bar db + (da+b\bar c)j,$$
where $j$ is matrix satisfying $\bar j=-j$.
 A: Let $x^2+ax+b\in\mathbb{F}_q[x]$ be an irreducible polynomial one of whose roots is a generator of the cyclic group $\mathbb{F}_{q^2}^\times$ of order $q^2-1$.  Define
$$A:=\begin{bmatrix}0&-b\\1&-a\end{bmatrix}\,.$$
Show that the order of $A$ is precisely $q^2-1$.
A: I will try to answer some of the motivation part of your post. Thanks to reuns's comment below, I realize now that I am making the assumption that $q$ is an odd prime power. I will first show how one may embed $\mathbb{F}_{q^2}$ in the matrix space $M_2(\mathbb{F}_q)$. We start with a finite field $\mathbb{F}_q$. We would like to build $\mathbb{F}_{q^2}$ from it. There is a standard construction for that. First one finds an irreducible (let us say monic) quadratic polynomial, say
$ f(x) = x^2 + ax + b \in \mathbb{F}_q[x] $
and then defines $\mathbb{F}_{q^2}$ to be $\mathbb{F}_q[x]/(f(x))$. Let
$\delta = a^2 - 4 b$
be the discriminant of $f$. Then we could alternatively have defined $\mathbb{F}_{q^2}$ from $\mathbb{F}_q$ by adjoining $\sqrt{\delta}$ to it. In other words,
$\mathbb{F}_q[y]/(y^2-\delta) \simeq \mathbb{F}_{q^2}$.
So an arbitrary element $u$ of $\mathbb{F}_{q^2}$ can be written as:
$u = c + d\sqrt{\delta}$,
where $c$ and $d$ are elements of $\mathbb{F}_q$. We would like to map $\sqrt{\delta}$ to the element
$ \left( \begin{array}{cc} 0 & \delta \\
                           1 & 0 \end{array} \right) \in GL(2;\mathbb{F}_q)$.
Note that an element $u$ as above, gets then mapped to
$ \left( \begin{array}{cc} c & \delta d \\
                           d & c \end{array} \right)$.
I am sure that using group actions may make the above construction cleaner (indeed, see Daniel Schepler's argument in the comments below), but at least it is explicit. We have thus found an embedding $f: \mathbb{F}_{q^2} \to M_2(\mathbb{F}_q)$.
The rest of this answer comes directly from Jyrki Lahtonen's answer below, as well as his comment. I include it here for completeness (you can give the points to Jyrki Lahtonen for that part!).
Define
$J = \left( \begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array} \right)$
Note that $J^2 = I$, with $I$ being the identity. Then, for all $u \in \mathbb{F}_{q^2}$, we have $J f(u) = f(\bar{u}) J$.
One can now check that the map $F$ which maps $u_1 + j u_2$ to $f(u_1) + J f(u_2)$ is indeed an isomorphism, as required. Thank you Jyrki Lahtonen once more for this part of the answer. 
A: The main question (the part with Cayley-Dickson) follows from the Skolem-Noether theorem.
Let's denote $K=\Bbb{F}_q, L=\Bbb{F}_{q^2}$, and for all $z\in L$ let $z^q=\overline{z}$ be the Frobenius automorphism. As the other answers have explained there exist ways of embedding $L$ into $M_2(K)$. Let's fix one such embedding $\phi:L\to M_2(K)$. Then $z\mapsto \phi(\overline{z})$ is another embedding of $L$, so by Skolem-Noether there exists an invertible matrix $u\in M_2(K)$ such that $u\phi(z)=\phi(\overline{z})u$ for all $z\in L$. Identifying $L$ with $\phi(L)$ allows us to rewrite this as
$$uz=\overline{z}u\quad\text{for all $z\in L$.}\qquad(*)$$
A priori there is no reason to think that $u^2$ would be equal to the identity. However, we can always arrange that to be the case. Namely, if $c\in L$ is arbitrary, it follows that $cz=zc$ for all $z\in L$ implying that $u'=uc$ can take the role of $u$ in equation $(*)$. Actually, the double centralizer theorem tells us that any two matrices satisfying $(*)$ are gotten from each other by multiplication by an element of $L$.
Anyway, applying $(*)$ twice tells us that
$$u^2z=u(uz)=u(\overline{z}u)=(u\overline{z})u=(zu)u=zu^2$$
for all $z\in L$. In other words $u^2$ commutes with all the matrices in $L$. Trivially $u^2$ commutes with $u$. The sum of subspaces $L+uL$ must be direct, and hence all of $M_2(K)$. We have just shown that $u^2$ is in the center of $M_2(K)$. Therefore $u^2$ is a scalar matrix, and we can think of it as an element $u^2=\alpha\in K$.
But, for all $c\in L$
$$(uc)^2=u(cu)c=u^2\overline{c}c=u^2N(c),$$
where $N:L\to K, z\mapsto z\overline{z}$ is the norm map. In the case of finite fields the norm map is surjective, so we can find an element $c_0$ such that $N(c_0)=1/\alpha$.
Therefore
$$
j=uc_0
$$
satisfies the relation $j^2=1$ as well as the relation $jz=\overline{z}j$ for all $z\in L$
as prescribed.
