Since the maximum order of an element of $\mathbb{Z}_n^* $ Is $\lambda(n)$, where $\lambda$ is the Carmichael function, we must have $\lambda(n)|6$. In particular if for an odd prime $p|n$ we must have $p-1|6$ so $p\leq 7$. for $p=2$ we have at most $ 2^3|n$ because $\lambda(8)=2$. For $p=2$ we have at most $3^2|n$ because $\lambda(9)=6$. $p=5$ can't happen because $4\nmid 6$ finally the biggest power of $7$ is $7^1$ because $\lambda(7)=6$ so the maximum $n$ is $$n=2^33^27=504$$

Official answer:504 Above: WOW

Nice question!

Clearly $n$ is even, take $v_2(n)$ and suppose that $v_2(n)\geq 4$ then $m^6\equiv 1 \pmod 16$ for all $(5,16)=1$ but $5^6\equiv 1 \pmod 16$ then $v_2(n)\leq 3$ and $m^6\equiv 1 \pmod 8$ works, then if $n$ is even iff $8$. Suppose that $5\mid n$ then $m^6\equiv 1\pmod 5$ for all $(m,5)=1$ and take $m=3$ for a contradiction. Then $(n+5,n)=1$ then $(n+5)^6\equiv 1 \pmod n$ then $n\mid 504\cdot 31$ Suppose that $n=504\cdot 31$ then $m^6\equiv 1\pmod 31$ for all $(m,31)=1$ but $(3,31)=1$ and $3^6\equiv 16\pmod 31$ contradition. Then $n\leq 504$ but is easy to check $n=504$ works $\blacksquare$

MiltonMath12 wrote: Clearly $n$ is even, take $v_2(n)$ and suppose that $v_2(n)\geq 4$ then $m^6\equiv 1 \pmod 16$ for all $(5,16)=1$ but $5^6\equiv 1 \pmod 16$ then $v_2(n)\leq 3$ and $m^6\equiv 1 \pmod 8$ works, then if $n$ is even iff $8$. Suppose that $5\mid n$ then $m^6\equiv 1\pmod 5$ for all $(m,5)=1$ and take $m=3$ for a contradiction. Then $(n+5,n)=1$ then $(n+5)^6\equiv 1 \pmod n$ then $n\mid 504\cdot 31$ Suppose that $n=504\cdot 31$ then $m^6\equiv 1\pmod 31$ for all $(m,31)=1$ but $(3,31)=1$ and $3^6\equiv 16\pmod 31$ contradition. Then $n\leq 504$ but is easy to check $n=504$ works $\blacksquare$ Can someone produce a clearer version of this explanation?

assume,$n=2^a*p_1^{a_1}....p_n^{a_n}$. Now,since primitive roots exist modulo prime powers we have $p_i^{a_i-1}*{p_i-1} \mid 6$ implies no prime bigger than $7$ divides $n$ and highest power of $7$ is $1$ and $3$ is $2$.For power of $2$.notice that $19^6 \equiv 9 \pmod{16}$ and $8$ obviously works.Hence highest possible $n$ is $2^3*3^2*7$