[pfedak]

You're misreading the solution, the first part reads n=1, a trivial special case, not n congruent to 1 mod 4.

The statement doesn't hold for e.g. n=5. Taking m=2 gives the permutation (1 2 4 3), which is odd, and thus cannot have a square root.