Is there an algorithm to generate size $n$ mutually orthogonal latin squares for $n \neq 2, 6$? Is there an algorithm to generate size $n$ mutually orthogonal latin squares for $n \neq 2, 6$?
For reference, I've been scanning several texts on combinatorics (Knuth's "The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1" and Lint's "A course in Combinatorics") to find such an algorithm.
I've already read this post, but it doesn't seem super helpful to my case.
 A: I can give an explicit construction of a pair of orthogonal Latin squares of order $n$ as long as $n>1$ and $n$ is not of the form $4k+2$ for some integer $k$. In this last case, I can at least give a citation.
First, assume $n$ is a prime power. Let $(\newcommand{\F}{\Bbb F}\F,\oplus,\otimes)$ be a finite field with $|F|=n$. We will think of the elements of $\F$ as the first $N$ nonnegative integers $\{0,1,\dots,n-1\}$ for convenience, such that $0$ is the additive identity and $1$ is the multiplicative identity. The operations $\oplus$ and $\otimes$ are not addition and multiplication modulo $n$ (except when $n$ is prime).
For each $k\in \F^\times$, we define an $n\times n$ Latin square $M^k$ as follows:
$$
M^k_{i,j}=k\otimes i\oplus j\qquad i,j\in \{0,1,\dots,n-1\}
$$
Note that I am using zero-indexing to describe the entries of $M^k$.
It is then easy to use the properties of finite fields to show that $\{M^1,M^2,\dots,M^{n-1}\}$ is a MOLS.
What about when $n$ is not a prime power? For this, the following "product" construction of Latin squares is useful. Let $L$ be a Latin square of order $\ell$, and $M$ be a Latin square of order $m$. For convenience, assume that the row indices, column indices, and labels for $L$ (resp. $M$) take values in $\{0,1\dots,\ell-1\}$ (resp. $\{0,1,\dots,m-1\}$). Then the product Latin square $L\times M$ is defined to be
$$
(L\times M)(i,j)=\ell\cdot M(i\,\%\, m,j \,\%\, m)+L(\lfloor i/m\rfloor,\lfloor j/m\rfloor)
$$
Here, $a\,\%\,b$ refers to the remainder of $a$ when divided by $b$, which is always in $\{0,1,\dots,b-1\}$.
You can then show that if $A_1$ and $A_2$ are orthogonal Latin squares of order $a$, and $B_1$ and $B_2$ are orthogonal Latin squares of order $b$, then $A_1\times B_1$ is orthogonal to $A_2\times B_2$. Using this construction, along with the existence of orthogonal Latin squares for all prime powers except for $2^1$, you can prove that two orthogonal Latin squares exist for all $n$, except when $n\equiv 2\pmod 4$. To do this, factorize $n$ into prime powers, find an orthogonal pair of each prime power order, then combine them together with the product. When $n=4k+2$, this method fails since there do not exist orthogonal squares of order $2$.
For the exception case $n=4k+2$, there is a construction, but it is much more complicated. A complete proof is given in section 4.4 of Combinatorial Designs and Tournaments, by Ian Anderson, but it is too involved for me to reproduce here.
